记录编号	326765	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	404	是否通过	通过
代码语言	C++	运行时间	2.796 s
提交时间	2016-10-21 14:42:59	内存使用	4.31 MiB

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 0x7fffffff
#define ll long long
using namespace std;
int n,m,q,be[110],rank[110];
int f[110][110][110];
struct node{int id;int d;}e[110];
bool cmp(node a,node b){return a.d<b.d;}
inline ll read()
{
    ll x=0,g=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')g=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*g;
}
inline int read2()
{
    int  x=0,g=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')g=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*g;
}
inline void outint(int _out){if(_out >= 10) outint(_out/10); putchar(_out%10+48);}
inline int find(int x)
{
    int l=1,r=n,ans=0;
    while(l<=r){
    	int mid=(l+r)>>1;
    	if(e[mid].d<=x)l=mid+1,ans=mid;
    	else r=mid-1;
    }return ans;
}
inline int upper(int w,int s,int x)
{ 
    int l=1,r=n,ans=0;
    while(l<=r){
    	int mid=(l+r)>>1;
    	if(f[w][s][mid]<=x)l=mid+1,ans=mid;
    	else r=mid-1;
    }return ans;
}
int main()
{
 	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	register int i,j,k;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=n;i++)e[i].d=read2(),e[i].id=i;
	std::sort(e+1,e+1+n,cmp);
	for(int k=0;k<=n+1;k++)
		for(int i=1;i<=n+1;i++)
			for(int j=1;j<=n+1;j++)
				f[k][i][j]=int(1e9)+1;
	for(i=1;i<=n;i++)f[0][i][i]=0;
	for(i=1;i<=n;i++)be[e[i].id]=i,rank[i]=e[i].id;
	for(i=1;i<=m;i++)
	{
		int u,v,w;
		u=read2(),v=read2(),w=read2();//u=be[u],v=be[v];
		if(f[0][u][v]>w)f[0][u][v]=f[0][v][u]=w;
	}
	for(k=1;k<=n;k++){
	        memcpy(f[k],f[k-1],sizeof f[k]);
	  	for(i=1;i<=n;i++)
	     	   for(j=1;j<=n;j++)
		     if(f[k][i][j]>f[k-1][i][rank[k]]+f[k-1][rank[k]][j])
                         f[k][i][j]=f[k][i][rank[k]]+f[k][rank[k]][j];		
	}
       	for(k=0;k<=n;k++)
	     for(i=1;i<=n;i++){
		std::sort(f[k][i]+1,f[k][i]+1+n);
	}
	while(q--){
		int s,ans=0,c,t;
		s=read2(),c=read2(),t=read2();//s=be[s];
		int w=find(c);
                ans=upper(w,s,t);
		printf("%d\n",ans-1);
	}return 0;
}