记录编号	327475	评测结果	AAAAAAATTT
题目名称	零食店	最终得分	70
用户昵称	nancheng58	是否通过	未通过
代码语言	C++	运行时间	3.226 s
提交时间	2016-10-22 07:37:03	内存使用	1.18 MiB

#include<iostream>
#include<cstdio>
#define MAXN 101
#define MAXM 10001
#define LL long long
using namespace std;
LL u,v,n,m,k,tot,w[MAXN],cut,q[MAXM*10],head1,tail,head[MAXN],dis[MAXN];
bool b[MAXN];
struct data{int v,next,x;}e[MAXM*2];
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
void add(int u,int v,int z)
{
	e[++cut].v=v;
	e[cut].next=head[u];
	e[cut].x=z;
	head[u]=cut;
}
int spfa(int s,int l,int limi)
{
	head1=tail=1;
	for(int i=1;i<=n;i++) dis[i]=1e10,b[i]=false;
	q[1]=s;dis[s]=0;
	while(head1<=tail)
	{
		u=q[head1++];b[u]=false;
		for(int i=head[u];i;i=e[i].next)
		{
			v=e[i].v;
			if(dis[u]+e[i].x>l) continue;
			if(dis[v]>dis[u]+e[i].x)
			{
				dis[v]=dis[u]+e[i].x;
				if(!b[v]&&w[v]<=limi) b[v]=true,q[++tail]=v;
			}
		}
	}
	tot=0;
	for(int i=1;i<=n;i++)
	 if(dis[i]<=l) tot++;
	return tot-1;
}
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	int x,y,z;
	n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<=m;i++)
	{
		x=read(),y=read(),z=read(),
	  	add(x,y,z),add(y,x,z);
	}
	while(k--)
	{
		x=read(),z=read(),y=read();
		printf("%d\n",spfa(x,y,z));
	}
	return 0;
}