记录编号	326614	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	旺仔小馒头	是否通过	通过
代码语言	C++	运行时间	2.955 s
提交时间	2016-10-21 11:07:47	内存使用	4.85 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 110
#define inf 1e9+1
using namespace std;
int n,m,Q,r[maxn],f[maxn][maxn][maxn];
int init(){
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
struct node{
	int c,o;
}p[maxn];
int cmp(const node &x,const node &y){
	return x.c<y.c;
}
void Floyed(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f[k][i][j]=min(f[k-1][i][j],f[k-1][i][p[k].o]+f[k-1][p[k].o][j]);
	for(int i=0;i<=n;i++)
		for(int j=1;j<=n;j++)
			sort(f[i][j]+1,f[i][j]+1+n);
}
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	scanf("%d%d%d",&n,&m,&Q);
	int u,v,pos,t;
	for(int i=1;i<=n;i++){
		p[i].c=init();p[i].o=i;
		r[i]=p[i].c;
	}
	sort(p+1,p+1+n,cmp);sort(r+1,r+1+n);
	for(int k=0;k<=n+1;k++)
		for(int i=0;i<=n+1;i++)
			for(int j=0;j<=n+1;j++)
				f[k][i][j]=inf;
	for(int i=1;i<=m;i++){
		u=init();v=init();t=init();
		if(t<f[0][u][v])
			f[0][u][v]=f[0][v][u]=t;
	}
	for(int i=1;i<=n;i++)f[0][i][i]=0;
	Floyed();
	while(Q--){
		u=init();v=init();t=init();
		v=upper_bound(r+1,r+1+n,v)-r-1;
		pos=upper_bound(f[v][u]+1,f[v][u]+1+n,t)-f[v][u]-1;
		printf("%d\n",pos-1);
	}
	return 0;
}