记录编号	326630	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	岂是蓬蒿人	是否通过	通过
代码语言	C++	运行时间	2.502 s
提交时间	2016-10-21 11:19:52	内存使用	4.85 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define bignum 1000000001
#define maxx 110
using namespace std;
int n,m,r,topt,sum;
int c[maxx],dis[maxx][maxx][maxx];
struct node
{
	int x;
	int w;
}t[maxx];
int init()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int cmp(node a,node b)
{
	return a.x<b.x;
}
void floyed()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			dis[k][i][j]=min(dis[k-1][i][j],dis[k-1][i][t[k].w]+dis[k-1][t[k].w][j]);
		}
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		sort(dis[i][j]+1,dis[i][j]+n+1);
	}
}
int main()
{
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	n=init();m=init();r=init();
	for(int i=1;i<=n;i++)
	{
		t[i].x=init();
		t[i].w=i;
		c[i]=t[i].x;
	}
	sort(t+1,t+n+1,cmp);
	sort(c+1,c+n+1);
	for(int i=0;i<=n;i++)
	  for(int j=1;j<=n;j++)
		for(int k=1;k<=n;k++)
		  dis[i][j][k]=bignum;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		x=init();y=init();z=init();
		if(z<dis[0][x][y])
		dis[0][x][y]=dis[0][y][x]=z;
	}
	for(int i=1;i<=n;i++)dis[0][i][i]=0;
	floyed();
	for(int i=1;i<=r;i++)
	{
		int x,y,z;
		x=init();y=init();z=init();
		int pos=upper_bound(c+1,c+n+1,y)-c-1; 
		int tot=upper_bound(dis[pos][x]+1,dis[pos][x]+n+1,z)-dis[pos][x]-1;
		printf("%d\n",tot-1);
	}
	return 0;
}