记录编号	326588	评测结果	AAAAAAATTT
题目名称	零食店	最终得分	70
用户昵称	宋逸群	是否通过	未通过
代码语言	C++	运行时间	3.773 s
提交时间	2016-10-21 10:30:33	内存使用	5.81 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long ll;
struct node{ll y,next,v;}e[100100*2];
ll n,m,q,x,c,s,ans,len,Q[110000],Link[1100],v[1100],vis[1100],dis[1100],del[1100];
char buf[1<<15],*fs,*ft;
inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline ll read()
{
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(ll x,ll y,ll v)  {e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;}
void spfa(ll st)
{
	ll head=0,tail=1;
	memset(dis,10,sizeof(dis));
	Q[1]=st;  vis[st]=1;  dis[st]=0;
	while(++head<=tail)
	{
		ll x=Q[head];
		for(ll i=Link[x];i;i=e[i].next)
			if(dis[x]+e[i].v<dis[e[i].y]&&!del[e[i].y])
			{
				dis[e[i].y]=dis[x]+e[i].v;
				if(!vis[e[i].y])
				{
					Q[++tail]=e[i].y;
					vis[e[i].y]=1;
				}
			}
		vis[x]=0;
	}
}
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	n=read();  m=read();  q=read();
	for(ll i=1;i<=n;i++)  v[i]=read();
	for(ll i=1;i<=m;i++)
	{
		ll x=read(),y=read(),v=read();
		insert(x,y,v);  insert(y,x,v);
	}
	for(ll i=1;i<=q;i++)
	{
		ll x=read(),c=read(),s=read();
		memset(vis,0,sizeof(vis));
		memset(del,0,sizeof(del));
		for(ll j=1;j<=n;j++)  if(v[j]>c)  del[j]=1;  
		spfa(x);  ans=0;  del[x]=0;
		for(ll j=1;j<=n;j++)  if(!del[j]&&dis[j]<=s&&j!=x)  ans++;
		for(ll j=1;j<=n;j++)  
			if(!del[j])
			{
				for(ll k=Link[j];k;k=e[k].next)
					if(!vis[e[k].y]&&del[e[k].y]&&e[k].y!=x&&e[k].v+dis[j]<=s)
					{
						vis[e[k].y]=1;
						ans++;
					}
			}
		printf("%lld\n",ans);
	}
	return 0;
}