记录编号	326540	评测结果	AAAAWWWTTT
题目名称	零食店	最终得分	40
用户昵称	Mealy	是否通过	未通过
代码语言	C++	运行时间	3.437 s
提交时间	2016-10-21 09:28:27	内存使用	0.64 MiB

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
 
 
const int pomax=186;
const int nmax=20086;
const int INF=1<<29;
 
 
int n,m,q;
int tmpu,tmpv,tmplen;
int tmps,pmax,emax;
int cnt=0;
 
 
class edge
{
public:
	int from,to;
	int len;
};
 
 
int val[pomax]={0};
bool tag[pomax]={0};
int dis[nmax];
vector<edge> edges;
vector<int > G[nmax];
 
 
inline void PreDo()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&val[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&tmpu,&tmpv,&tmplen);
		edges.push_back((edge){tmpu,tmpv,tmplen});
		G[tmpu].push_back(edges.size()-1);
		edges.push_back((edge){tmpv,tmpu,tmplen});
		G[tmpv].push_back(edges.size()-1);
	}
	
}
 
 
class T2
{
public:
	bool inqueue[nmax];
	queue<int > q;
	void SPFA(int tmps,int pmax,int emax)
	{
		cnt=0;
	 	for(int i=1;i<=n;i++)
		{
			dis[i]=INF;
		}
		dis[tmps]=0;
		memset(inqueue,0,sizeof(inqueue));
		q.push(tmps);
		inqueue[tmps]=1;
		while(!q.empty())
		{
			int tmpx=q.front();
			q.pop();
			inqueue[tmpx]=0;
			for(int i=0;i<G[tmpx].size();i++)
			{
				int tmpv=edges[G[tmpx][i]].to;
				if(dis[tmpv]>dis[tmpx]+edges[G[tmpx][i]].len)
				{
					dis[tmpv]=dis[tmpx]+edges[G[tmpx][i]].len;
					if(val[tmpv]<=pmax)
					{
						if(!inqueue[tmpv])
						{
							q.push(tmpv);
							inqueue[tmpv]=1;
						}
					}
				}		
			}
		}
	}
}FJ;
 
 
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	PreDo();
	for(int x=1;x<=q;x++)
	{
		scanf("%d%d%d",&tmps,&pmax,&emax);
		FJ.SPFA(tmps,pmax,emax);
		for(int i=1;i<=n;i++)
		{
			if(dis[i]<=emax&&i!=tmps)
			{
				cnt++;
			}
		}
		printf("%d\n",cnt);
		cnt=0;
	}
	return 0;
}