记录编号	427764	评测结果	AAAAAAAAAA
题目名称	2507.零食店	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	1.183 s
提交时间	2017-07-23 09:04:55	内存使用	5.42 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cctype>

using namespace std;

const int INF=1e9+1;

inline int read(){
	int _x=0; char ch; bool flag=false;
	while(ch=getchar(),!isdigit(ch)) ch=='-'?flag=true:false;
	while(_x=_x*10+ch-'0',ch=getchar(),isdigit(ch));
	return flag?-_x:_x;
}

char out[100];int len;
inline void print(int x){
	if(x==0) putchar('0');
	len=0;
	while(x!=0){
		out[len++]=x%10+'0';
		x/=10;
	}
	while(len){
		len--;
		putchar(out[len]);
	}
	putchar('\n');
}

struct node{ int val,pos; }a[110];
int n,m,q,ans[110][110][110],g[110][110],hash[110];
bool cmp(const node &a,const node &b){return a.val<b.val;}
inline int min(int a,int b){return a<b?a:b;}

inline int find(int c){
	int l=1,r=n,mid,re=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(a[mid].val<=c) re=mid,l=mid+1;
		else r=mid-1;
	}
	return re;
}

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].val=read(),a[i].pos=i;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) hash[a[i].pos]=i;
	for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            g[i][j]=INF;
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		u=hash[u]; v=hash[v];
		g[u][v]=min(g[u][v],w);
		g[v][u]=min(g[v][u],w);
	}
	for(int i=1;i<=n;i++) g[i][i]=0;
	memcpy(ans[0],g,sizeof(g));
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][k]!=INF&&g[k][j]!=INF)
					g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
		memcpy(ans[k],g,sizeof(g));
	}
	a[n+1].val=INF;
	for(int i=1;i<=q;i++){
		int s=read(),c=read(),d=read(),pos=0,sum=0;
		s=hash[s];
		pos=find(c);
		for(int j=1;j<=n;j++)
			if(s!=j&&ans[pos][s][j]<=d)
				sum++;
		print(sum);
	}
	return 0;
}