记录编号	441988	评测结果	AAAAAAAAAA
题目名称	零食店	最终得分	100
用户昵称	xzz_233	是否通过	通过
代码语言	C++	运行时间	1.684 s
提交时间	2017-08-25 22:58:26	内存使用	8.16 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
#define Fname "snackstore"
using namespace std;
#define rep(a,b,c) for(rg ll a=b;a<=c;a++)
#define drep(a,b,c) for(rg ll a=b;a>=c;a--)
#define erep(a,b) for(rg ll a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define t (dis[i])
typedef long long ll;
il ll gi(){
    rg ll x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int maxn=101,maxm=10010;
ll v[maxn];
ll f[maxn][maxn][maxn],n,m,q;
struct haha{ll v,id;}s[maxn];
bool operator <(haha a,haha b){return a.v<b.v;}
int main(){
	freopen(Fname".in","r",stdin);
	freopen(Fname".out","w",stdout);
    n=gi(),m=gi(),q=gi();
    rep(i,1,n)s[i].v=gi(),s[i].id=i;
    sort(s+1,s+n+1);
    rep(i,1,n)v[i]=s[i].id;
    ll a,b,l;
    rep(i,1,n)rep(j,i+1,n)f[0][i][j]=f[0][j][i]=1e9+1;
	rep(i,1,m)a=gi(),b=gi(),l=gi(),f[0][a][b]=f[0][b][a]=min(f[0][a][b],l);
    rep(k,1,n)rep(i,1,n)rep(j,1,n)f[k][i][j]=min(f[k-1][i][j],f[k-1][i][v[k]]+f[k-1][v[k]][j]);
    rep(k,0,n)rep(i,1,n)sort(f[k][i]+1,f[k][i]+1+n);
    rep(i,1,q){
    	ll ss=gi(),c=gi(),d=gi();
    	ll k,l=0,r=n;
    	while(l<r)
    		if(s[(l+r>>1)+1].v<=c)l=(l+r>>1)+1;
    		else r=l+r>>1;
    	k=l;
    	l=0,r=n;
    	while(l<r)
			if(f[k][ss][(l+r>>1)+1]<=d)l=(l+r>>1)+1;
    		else r=l+r>>1;
    	#ifdef xzz
    	printf("%I64d\n",l-1);
    	#else
    	printf("%lld\n",l-1);
    	#endif
    }
    return 0;
}