记录编号	327620	评测结果	AWWWWWWWWT
题目名称	零食店	最终得分	10
用户昵称	dududu	是否通过	未通过
代码语言	C++	运行时间	2.989 s
提交时间	2016-10-22 11:43:11	内存使用	4.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define d(k,i,j) dis[k][i][j]
#define exd(k) dis[k]
#define F(i,j) for(int i=1;i<=j;i++)
#define KN 110
int dis[KN][KN][KN];
int N,M,Q;
int pow[KN];
struct S
{
	int lable,value;
}node[KN];

bool my_cmp(const S a,const S b){
	return a.value<b.value;
}

int getnum(){
	char tmp=getchar();
	int res=0;
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp<='9'&&tmp>='0'){
		res=res*10+tmp-'0';
		tmp=getchar();
	}	
	return res;
}

void init()
{
	//------read------
	scanf("%d%d%d",&N,&M,&Q);
	F(i,N){
		node[i].lable=i;
		node[i].value=getnum();
		d(0,i,i)=0;
	}
	memset(dis,0x3f,sizeof dis);
	
	int u,v,l;
	F(i,M){
		u=getnum(),v=getnum(),l=getnum();
		if(d(0,u,v)<l) continue;
		d(0,u,v)=d(0,v,u)=l;
	}
	//-------prehandle--------
	sort(node+1,node+1+N,my_cmp);
	F(i,N) pow[i]=node[i].value;
}

void floyd()
{
	F(k,N){
		memcpy(exd(k),exd(k-1),sizeof exd(k));
		int pos=node[k].lable;
		F(i,N){
			F(j,N){
				if(d(k,i,j)>d(k,i,pos)+d(k,pos,j))
					d(k,i,j)=d(k,i,pos)+d(k,pos,j);
			}
		}
	}
	for(int k=0;k<=N;k++){
		F(i,N) sort(dis[k][i]+1,dis[k][i]+1+N);
	}
}

void query()
{
	int start,max_v,cost;
	F(i,Q){
		start=getnum(),max_v=getnum(),cost=getnum();
		int pos=lower_bound(pow+1,pow+1+N,max_v)-pow;
		int ans=lower_bound(dis[pos][start]+1,dis[pos][start]+1+N,cost)-dis[pos][start];
		if(d(pos,start,ans)>cost) ans--;
		printf("%d\n",ans);
	}
}
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	init();
	floyd();
	query();
	return 0;
}