记录编号	326679	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.517 s
提交时间	2016-10-21 12:32:27	内存使用	8.28 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010,maxl=1e+9+1;
struct edge{
	int f,t,l;
	edge(int F=0,int T=0,int L=0){f=F;t=T;l=L;}
}w[N];
int n,m,q,c[N],A[N],B[N],head[N],tail[N],next[N];
inline int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
inline bool cmp(const int x,const int y){
	return c[x]<c[y];
}
inline void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
queue<int> Q;
int dis[N],dp[110][110][110];
inline void spfa(int s,int C){
	while (!Q.empty()){
		int v=Q.front();Q.pop();
		if (c[v]>C&&v!=s) continue;
		for (int i=head[v];i;i=next[i])
		if (dis[w[i].t]>dis[v]+w[i].l)
			dis[w[i].t]=dis[v]+w[i].l,Q.push(w[i].t);
	}
}
inline int find(int x,int *A,int l,int r){//找到对应的最大点权 
	while (l!=r){
		int mid=(l+r)>>1;
		if (A[mid+1]<=x) l=mid+1;else r=mid;
	}
	return l;
}
char s[20];
inline void print(int x){
	if (!x) {puts("0");return;}
	int l=0;for (;x;x/=10) s[l++]=x%10;
	while (l--) putchar(s[l]+'0');putchar('\n');
}
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	n=read();m=read();q=read();
	for (int i=1;i<=n;i++) A[i]=i,c[i]=read();
	for (int i=1;i<=m;i++){
		w[i].f=read();w[i].t=read();w[i].l=read();
		w[i+m]=w[i];
		swap(w[i].f,w[i].t);
		add(w[i].f,i);add(w[i].t,i+m);
	}
	sort(A+1,A+n+1,cmp);
	for (int i=1;i<=n;i++) B[i]=c[A[i]];
	for (int s=1;s<=n;s++){//源点为i号点 
		for (int i=1;i<=n;i++) dis[i]=maxl;dis[s]=0;
		Q.push(s);spfa(s,0);
		for (int i=1;i<=n;i++) dp[s][0][i]=dis[i];
		sort(dp[s][0]+1,dp[s][0]+n+1);
		//printf("S=%d\n",s);
		for (int j=1;j<=n;j++){//添加A[j]号点 
			Q.push(A[j]);spfa(s,c[A[j]]);
			for (int i=1;i<=n;i++) dp[s][j][i]=dis[i];
			//printf("C<=%d ",c[A[j]]);
			//for (int i=1;i<=n;i++) printf("%d ",dis[i]);puts("");
			sort(dp[s][j]+1,dp[s][j]+n+1);
		}
	}
	while (q--){
		int s=read(),c=read(),d=read();
		c=find(c,B,0,n);
		int ans=find(d,dp[s][c],0,n)-1;
		print(ans);
		//printf("%d\n",ans);
	}
	return 0;
}