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

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100+10;
int f[maxn][maxn][maxn];
inline void read(int &x){
	x=0;
	bool flag=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')
			flag=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	if(flag)
		x=-x;
}
struct T{
	int id,v;
	bool operator<(const T& a)const{
		return v<a.v;
	}
}A[maxn];
int v[maxn];
int V[maxn];
int main(){
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	int n,m,q;
	scanf("%d %d %d",&n,&m,&q);
	for(int k=0;k<=n+1;k++)
		for(int i=0;i<=n+1;i++)
			for(int j=0;j<=n+1;j++)
				f[k][i][j]=(int)1e9+1;
	int x,y,z;
	for(int i=1;i<=n;i++){
		scanf("%d",&V[i]);
		A[i].v=V[i];
		A[i].id=i;
	}
	std::sort(A+1,A+n+1);
	for(int i=1;i<=n;i++)
		v[i]=A[i].v,f[0][i][i]=0;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		f[0][x][y]=f[0][y][x]=min(f[0][y][x],z);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
				f[k][i][j]=min(f[k-1][i][j],f[k][i][j]);
			for(int j=1;j<=n;j++)
				f[k][i][j]=min(f[k-1][i][A[k].id]+f[k-1][A[k].id][j],f[k-1][i][j]);
		}
	for(int k=0;k<=n;k++)
		for(int i=1;i<=n;i++)
			std::sort(f[k][i]+1,f[k][i]+n+1);
	for(int i=1;i<=q;i++){
		read(x),read(y),read(z);
		int ans;
		int l=0,r=n;
		int mid;
		while(l+1<r){
			mid=(l+r)>>1;
			if(v[mid]>y)
				r=mid;
			else l=mid;
		}
		if(v[r]<=y)
			ans=r;
		else ans=l;
		int ll=0,rr=n;
		while(ll+1<rr){
			mid=(ll+rr)>>1;
			if(f[ans][x][mid]>z)
				rr=mid;
			else ll=mid;
		}
		int anss;
		if(f[ans][x][rr]<=z)
			anss=rr;
		else anss=ll;
		printf("%d\n",anss-1);
	}
return 0;
}