记录编号	594789	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	1.996 s
提交时间	2024-10-05 11:51:50	内存使用	8.41 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000000001
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node{
	ll id,val;
}pnt[110];
struct node_line{
	ll l,r,val;
}line[100010];
ll n,m,q;
ll len[110][110][110],lsh[110];
bool cmp(node a,node b){
	return a.val<b.val;
}
void floyd(){
	for(int i=0;i<=n;i++)for(int j=1;j<=n;j++)for(int u=1;u<=n;u++)len[i][j][u]=N;
	for(int i=1;i<=m;i++){
		ll u=line[i].l,v=line[i].r,w=line[i].val;
		len[0][u][v]=min(w,len[0][u][v]);
		len[0][v][u]=min(w,len[0][v][u]);
	}
	for(int k=1;k<=n;k++){
		lsh[k]=pnt[k].val;
		int i=pnt[k].id;
		for(int u=1;u<=n;u++){
			for(int v=1;v<=n;v++){
				if(v==u||v==i||u==i){
					len[k][u][v]=len[k-1][u][v];
//					if(len[k][u][v]!=N)cout<<len[k][u][v]<<" ";
//					else cout<<"-1 ";
					continue;
				}
				len[k][u][v]=min(len[k-1][u][v],len[k-1][u][i]+len[k-1][i][v]);
//				len[k][v][u]=min(len[k-1][v][u],len[k-1][v][i]+len[k-1][i][u]);
//				if(len[k][u][v]!=N)cout<<len[k][u][v]<<" ";
//				else cout<<"-1 ";
			}
//			cout<<endl;
		}
//		cout<<"\n---------\n";
	}
}
ll ef(ll h){
	ll l=0,r=n;
	while(l<r){
		ll mid=(l+r+1)/2;
		if(lsh[mid]<=h)l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
	freopen("snackstore.in","r",stdin);
	freopen("snackstore.out","w",stdout);
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++){
		pnt[i].id=i,pnt[i].val=read();
	}
	for(int i=1;i<=m;i++)line[i].l=read(),line[i].r=read(),line[i].val=read();
	sort(pnt+1,pnt+1+n,cmp);
	floyd();
	for(int i=1;i<=q;i++){
		ll x=read(),y=read(),z=read();
		ll h=ef(y),ans=0;
//		cout<<h<<endl;
		for(int j=1;j<=n;j++){
			if(len[h][x][j]<=z&&j!=x){
				ans++;
//				cout<<j<<" ";
			}
		}
//		cout<<endl;
//		cout<<ans<<endl;
		printf("%lld\n",ans);
	}
	return 0;
}