记录编号	326527	评测结果	AAAAAAATTT
题目名称	零食店	最终得分	70
用户昵称	农场主	是否通过	未通过
代码语言	C++	运行时间	5.694 s
提交时间	2016-10-21 09:07:18	内存使用	4.24 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define maxn 101 
#define INF 0x7fffffff
using namespace std;
typedef long long ll; 
class edge{
public:
	int from,to,dis;
};
class poi{
public:
	int x,id;
	bool operator < (const poi p)const{
		return x<p.x;
	}
};
vector<edge> G[maxn];
poi c[maxn]={0};
int n,m,q;
int d[maxn][maxn][maxn]={0};
int can[maxn]={0};
bool inq[maxn]={0};
int C[maxn]={0};
inline void spfa(int s,int* d){
	for (int i=1;i<=n;i++){
		d[i]=INF;
	}
	memset(inq,0,sizeof(inq));
	queue<int> q; q.push(s);
	inq[s]=1; d[s]=0;
	while(!q.empty()){
//		printf("%d ",q.front());
		int x=q.front(); q.pop(); inq[x]=0;
		for (int i=0;i<G[x].size();i++) {
			edge& e=G[x][i];
			if (d[e.to]>d[e.from]+e.dis){
				d[e.to]=d[e.from]+e.dis;
				if (!inq[e.to]&&!can[e.to]){
					inq[e.to]=1;
					q.push(e.to);
				}
			}
		}
	}
	sort(d+1,d+n+1); 
//	printf("\n");
}
inline void solve(int p){
	memset(can,0,sizeof(can));
	int cap=c[p].x;
	for (int i=1;i<=n;i++){
		if (c[i].x>cap) can[c[i].id]=1;
	}
	for (int i=1;i<=n;i++){
		spfa(i,d[p][i]);
	}
}
inline void pre(){
	for (int i=0;i<=n;i++){
		solve(i);
	}
}
inline int lower_bound(int x,int* c){
	int l=0,r=n,mid;
	while(l<r){
		mid=(l+r>>1)+1;
//		printf("%d %d\n",c[mid],x);
		if (c[mid]>x){
			r=mid-1;
		}
		else l=mid;
	}
	return l;
}
inline void query(int s,int v,int dist){
	int q=lower_bound(v,C);
//	for (int i=1;i<=n;i++){
//		if (c[i].x<=v&&c[q].x<=c[i].x){
//			q=i;
//		}
//	}
//	if (p!=q) printf("%d %d\n",p,q);
	int ans=0;
/*	for (int i=1;i<=n;i++){
		if (d[q][s][i]<=dist){
			ans++;
//			printf("%d",q);
		}
	}*/
	ans=lower_bound(dist,d[q][s]);
//	if (lower_bound(dist,d[q][s])!=ans)printf("a");
	printf("%d\n",ans-1);
}
int in() {
	int a = 0;
	char c = getchar();
	while (!('0' <= c && c <= '9'))
		c = getchar();
	while ('0' <= c && c <= '9') {
		a = a * 10 + c - '0';
		c = getchar();
	}
	return a;
}

inline void read(){
	scanf("%d%d%d",&n,&m,&q);
	c[0].x=0; c[0].id=0;
	for (int i=1;i<=n;i++){
//		scanf("%d",&c[i].x);
		c[i].x=in();
		c[i].id=i;
	}
	sort(c,c+n+1);
	for (int i=0;i<=n;i++){
		C[i]=c[i].x;
//		printf("%d ",C[i]);
	}
	int u,v,w;
	for (int i=1;i<=m;i++){
//		scanf("%d%d%d",&u,&v,&w);
		u=in(),v=in(),w=in();
		G[u].push_back((edge){u,v,w});
		G[v].push_back((edge){v,u,w});
	}
	pre();
	for (int i=1;i<=q;i++){
		int s,c,d;
//		scanf("%d%d%d",&s,&c,&d);
		s=in(),c=in(),d=in();
		query(s,c,d);
	}
}
int main(){
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	read();
	return 0;
}