记录编号	326999	评测结果	AAAAAAATTT
题目名称	2507.零食店	最终得分	70
用户昵称	gls1196	是否通过	未通过
代码语言	C++	运行时间	3.413 s
提交时间	2016-10-21 18:51:12	内存使用	9.15 MiB

/*
D1T2 ：类似于过路费，按照点权排序跑Floyed，dis[k][i][j] 表示经过前k小的点，i'j的最短距离。
	最后求答案二分得到最多能走前k各点，再次二分距离。

*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=105;
ll n,m,q,dis[maxn][maxn][maxn],val[maxn],id[maxn];
bool Cmp(const ll &x,const ll &y){
	return val[x]<val[y];
}
void Floyed(){
	memset(dis,0x1f,sizeof(dis));
	scanf("%lld%lld%lld",&n,&m,&q);ll u,v,w;
	for(int i=1;i<=n;i++)id[i]=i,scanf("%lld",&val[i]);
	sort(id+1,id+n+1,Cmp);
	while(m--){
		scanf("%lld%lld%lld",&u,&v,&w);
		dis[0][u][v]=dis[0][v][u]=min(dis[0][u][v],w);
	}
	for(int i=1;i<=n;i++)dis[0][i][i]=0;
	for(int k=1;k<=n;k++){
		memcpy(dis[k],dis[k-1],sizeof(dis[k-1]));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dis[k][i][j]=min(dis[k][i][j],dis[k][i][id[k]]+dis[k][id[k]][j]);
	}
	for(int k=0;k<=n;k++)
		for(int i=1;i<=n;i++)
			sort(dis[k][i]+1,dis[k][i]+n+1);
	sort(val+1,val+n+1);
}
void Query(){ll u,v,d;
	while(q--){
		scanf("%lld%lld%lld",&u,&v,&d);
		ll p=upper_bound(val+1,val+n+1,v)-val-1;
		ll ans=upper_bound(dis[p][u]+1,dis[p][u]+n+1,d)-dis[p][u]-1;
		printf("%lld\n",--ans);
	}
}
int main(){
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	Floyed();Query();return 0;
}