记录编号	327326	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	chad	是否通过	通过
代码语言	C++	运行时间	1.875 s
提交时间	2016-10-21 21:31:50	内存使用	4.74 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define FILE "snackstore"
 
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,ch=gc();
		while(ch<'0'||ch>'9')ch=gc();
		while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=gc();
		return x;
	}
}using namespace IO;
 
const int MAXN(105);
int n,m,q,pow[MAXN],dis[MAXN][MAXN][MAXN];
 
struct vertex{
	int x,p;
}v[MAXN];
inline bool operator<(const vertex& u,const vertex& v){
	return u.p<v.p;
}
 
void init(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++)
		v[i].x=i,v[i].p=read();
	std::sort(v+1,v+n+1);
	for(int i=1;i<=n;i++)
		pow[i]=v[i].p;
		
	for(int k=0;k<=n+1;k++)
		for(int i=1;i<=n+1;i++)
			for(int j=1;j<=n+1;j++)
				dis[k][i][j]=int(1e9)+1;
	for(int i=1;i<=n;i++)
		dis[0][i][i]=0;
		
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),l=read();
		if(l<dis[0][x][y])
			dis[0][x][y]=dis[0][y][x]=l;
	}
}
 
inline int rand32(){return ((rand()&1)<<30)|(rand()<<15)|rand();}
inline int rand(int l,int r){if(r<l)return l;return l+rand32()%(r-l+1);}
 
void floyd(){
	for(int k=1;k<=n;k++){
		memcpy(dis[k],dis[k-1],sizeof dis[k]);
		#define d(x,y) dis[k][x][y]
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(d(i,v[k].x)+d(v[k].x,j)<d(i,j))
					d(i,j)=d(i,v[k].x)+d(v[k].x,j);
	}
	for(int k=0;k<=n;k++)
		for(int i=1;i<=n;i++)
			std::sort(dis[k][i]+1,dis[k][i]+n+1);
}
 
int binary(int* a,int k){
	int left=0,right=n;
	while(left!=right){
		int mid=left+right;
		mid=(mid&1)+(mid>>1);
		if(a[mid]>k)right=mid-1;
		else left=mid;
	}
	return left;
}
 
void solve(){
	for(int Case=1;Case<=q;Case++){
		int i=read(),mxp=read(),mxd=read();
		printf("%d\n",binary(dis[binary(pow,mxp)][i],mxd)-1);
	}
}
 
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	
	init();
	floyd();
	solve();
	
	return 0;
}