记录编号	331673	评测结果	AAAAWWWTTT
题目名称	零食店	最终得分	40
用户昵称	半汪	是否通过	未通过
代码语言	C++	运行时间	4.770 s
提交时间	2016-10-27 20:56:09	内存使用	9.63 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int dis[110][110][110],v[110],c[110],a0[110];
int cnt[110][110][110],head[110];
int n,m,q,tot=0,N=1;
int Max(int x,int y){if(x>y)return x;return y;}
int Min(int x,int y){if(x<y)return x;return y;}
struct Edge{
	int to,next,w;
}edge[20010];
void Add(int x,int y,int w){
	edge[++tot].to=y;
	edge[tot].w=w;
	edge[tot].next=head[x];
	head[x]=tot;
}
struct Node{
	int id,dis,cc;
	Node(int x,int z,int y){
		id=x;dis=y;cc=z;
	}
	bool operator<(const Node&a)const{
		return dis>a.dis;
	}
};
#define p edge[i].to
priority_queue<Node>que;
void djs(int s){
	dis[s][s][0]=0;
	que.push(Node(s,0,0));
	while(!que.empty()){
		Node node=que.top();que.pop();
		int x=node.id,cc=node.cc;
		if(dis[s][x][cc]!=node.dis)continue;
		int z;
		if(x!=s)z=Max(cc,c[x]);
		else z=0;
		for(int i=head[x];i;i=edge[i].next){
			if(dis[s][p][z]>dis[s][x][cc]+edge[i].w){
				dis[s][p][z]=dis[s][x][cc]+edge[i].w;
				que.push(Node(p,z,dis[s][p][z]));
			}
		}
	}
}
int main(){
    freopen("snackstore.in","r",stdin);
    freopen("snackstore.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);
		a0[i]=v[i];
	}
	sort(a0+1,a0+n+1);
	a0[1]=1;
	for(int i=2;i<=n;i++)if(a0[i]!=a0[i+1])a0[++N]=a0[i];
	for(int i=1;i<=n;i++){
		c[i]=lower_bound(a0+1,a0+N+1,v[i])-a0;
	}
	for(int i=1;i<=m;i++){
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		Add(x,y,w);
		Add(y,x,w);
	}
	memset(dis,0x7f,sizeof(dis));
	memset(cnt,0x7f,sizeof(cnt));
	for(int i=1;i<=n;i++)djs(i);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cnt[i][0][j]=dis[i][j][0];
	for(int i=1;i<=n;i++){
		for(int k=1;k<=N;k++){
			for(int j=1;j<=n;j++){
				cnt[i][k][j]=Min(cnt[i][k-1][j],dis[i][j][k]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=N;j++){
			sort(cnt[i][j]+1,cnt[i][j]+1+n);
		}
	}
	while(q--){
		int s,c1,d1;
		scanf("%d%d%d",&s,&c1,&d1);
		int k=lower_bound(a0+1,a0+N+1,c1)-a0;
		while(a0[k]>c1)k--;
		if(k>N)k=N;
		int ans=0;
		ans=lower_bound(cnt[s][k]+1,cnt[s][k]+n+1,d1)-cnt[s][k];
		while(ans>1&&cnt[s][k][ans]>d1)ans--;
		ans--;
		printf("%d\n",ans);
	}
    return 0;
}