记录编号	326697	评测结果	AAAAAAATTT
题目名称	零食店	最终得分	70
用户昵称	Marvolo	是否通过	未通过
代码语言	C++	运行时间	3.120 s
提交时间	2016-10-21 13:00:48	内存使用	13.71 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int n,m,q,dmax,h,ans,qd,i,x,y,Z;
int z[110],d[110],s[110];
int ld[110][110];
bool v[110],bh[110];
vector <int> l[110],l2[110];

inline int read(){
	int p=0,c=getchar();
	while (c<'0'||c>'9')	c=getchar();
	while (c>='0'&&c<='9')	p=p*10+c-48,c=getchar();
	return p;
}
inline int min(int a,int b){return (a<b)?a:b;}

inline void SPFA(){
	int t=1,w=0,dd=0,i=0;
	ans=0;
	memset(z,0,sizeof(z));	memset(d,0x3f3f3f3f,sizeof(d));	memset(v,0,sizeof(v));
	memset(bh,0,sizeof(bh));
	z[t]=qd;	v[qd]=1;	bh[qd]=1;	d[qd]=0;
	while (w!=t){
		w=(w+1)%n;	dd=z[w];	v[dd]=0;
		for (i=0;i<l[dd].size();i++)
			if (d[dd]+l2[dd][i]<=dmax&&d[dd]+l2[dd][i]<d[l[dd][i]]){
				d[l[dd][i]]=d[dd]+l2[dd][i];
				if (!bh[l[dd][i]])	ans++,bh[l[dd][i]]=1;
				if (s[l[dd][i]]>h)	continue;   //超过限制不再松弛
				if (!v[l[dd][i]]){
					v[l[dd][i]]=1;	t=(t+1)%n;	z[t]=l[dd][i];	continue;	
				}
			}   //不能到都是扯淡
	}
	printf("%d\n",ans);
}

int main(){
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	n=read();	m=read();	q=read();
	for (i=1;i<=n;i++)	s[i]=read();
	memset(ld,0x3f3f3f3f,sizeof(ld));
	for (i=1;i<=m;i++){
		x=read();	y=read();	Z=read();
		if (x==y)	continue;
		ld[x][y]=min(ld[x][y],Z);
		if (ld[x][y]!=Z)	continue;
		l[x].push_back(y);	l[y].push_back(x);
		l2[x].push_back(Z);	l2[y].push_back(Z);
	}
	while (q--){
		qd=read();	h=read();	dmax=read();
		SPFA();
	}
	return 0;
}