记录编号	326929	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	1.662 s
提交时间	2016-10-21 17:36:37	内存使用	3.24 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define file(x) "snackstore."#x
namespace IStream{  
    const int L=1<<15;  
    char buffer[L],*S,*T;  
    inline char Get_Char()  
    {  
        if(S==T)  
        {  
            T=(S=buffer)+fread(buffer,1,L,stdin);  
            if(S==T) return EOF;  
        }  
        return *S++;  
    }  
    inline int gint()  
    {  
        char c;  
        int re=0;  
        for(c=Get_Char();c<'0'||c>'9';c=Get_Char());  
        while(c>='0'&&c<='9')  
            re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();  
        return re;  
    }  
}  
using IStream::gint;
using std::min;
using std::sort;
const int MAXN=110;
int n,m,q,dis[MAXN][MAXN][MAXN],v[MAXN],vv[MAXN];
bool cmpvv(int a,int b){
	return v[a]<v[b];
}
int bis(int x,int* tar){
	int l=0,r=n,mid;
	while(l<r){
		mid=l+r+1>>1;
		if(tar[mid]<=x) l=mid;
		else r=mid-1;
	}
	return l;
}
int lisan[MAXN];
int Main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	n=gint(),m=gint(),q=gint();
	for(int i=1;i<=n;i++) v[i]=gint(),vv[i]=i,lisan[i]=v[i];
	sort(vv+1,vv+1+n,cmpvv);
	for(int i=1;i<=n;i++) lisan[i]=v[vv[i]];
	for(int k=0;k<=n;k++) for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) dis[k][j][i]=1e9+1;
	for(int i=1;i<=m;i++){
		int u,v,t;
		u=gint();
		v=gint();
		t=gint();
		dis[0][u][v]=dis[0][v][u]=min(dis[0][u][v],t);
	}
	for(int i=1;i<=n;i++) dis[0][i][i]=0;
	for(int vid=1;vid<=n;vid++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) 
				dis[vid][i][j]=min(dis[vid-1][i][j],dis[vid-1][i][vv[vid]]+dis[vid-1][vv[vid]][j]);
	for(int i=0;i<=n;i++) for(int j=1;j<=n;j++) {
		sort(dis[i][j]+1,dis[i][j]+1+n);
	}
	for(int i=1;i<=q;i++) {
		int s,c,d;
		s=gint();
		c=gint();
		d=gint();
		printf("%d\n",bis(d,dis[bis(c,lisan)][s])-1);
	}
	return 0;
}
int enter=Main();
int main(){
}