记录编号	326583	评测结果	AAAAAAATTT
题目名称	零食店	最终得分	70
用户昵称	Cydiater	是否通过	未通过
代码语言	C++	运行时间	4.740 s
提交时间	2016-10-21 10:27:49	内存使用	107.44 MiB

//B
//by Cydiater
//2016.10.19
#include <iostream>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <string>
using namespace std;
#define ll long long
#define up(i,j,n)		for(int i=j;i<=n;i++)
#define down(i,j,n)		for(int i=j;i>=n;i--)
#define FILE "snackstore"
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline ll read(){
	char ch=getchar();ll x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct Ask{
	ll s,c,d,ans,id;
	Ask(){ans=0;}
}ask[MAXN];
struct edge{
	ll x,y,next,v;
}e[MAXN];
struct Node{
	ll id,c;
}node[MAXN];
ll N,M,Q,f[205][205],LINK[MAXN],len=0,added=1,cnt[MAXN],C[MAXN];
namespace solution{
	inline void insert(int x,int y,ll v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
	inline bool cmp1(Ask x,Ask y){return x.c<y.c;}
	inline bool cmp2(Node x,Node y){return x.c<y.c;}
	inline bool cmp3(Ask x,Ask y){return x.id<y.id;}
	void init(){
		memset(f,10,sizeof(f));
		N=read();M=read();Q=read();
		up(i,1,N){node[i].c=read();node[i].id=i;C[i]=node[i].c;}
		up(i,1,M){
			ll x=read(),y=read(),v=read();
			insert(x,y,v);
			insert(y,x,v);
			f[x][y]=min(f[x][y],v);
			f[y][x]=f[x][y];
		}
		up(i,1,Q){
			ask[i].s=read();ask[i].c=read();ask[i].d=read();ask[i].id=i;
		}
		sort(ask+1,ask+Q+1,cmp1);
		sort(node+1,node+N+1,cmp2);
	}
	void slove(){
		up(i,1,N)f[i][i]=0;
		up(i,1,Q){
			int c=ask[i].c,now=ask[i].s;bool flag=0;
			while(node[added].c<=c&&added<=N){
				int tmp=node[added].id;
				for(int h=LINK[tmp];h;h=e[h].next){
					f[tmp][e[h].y]=min(f[tmp][e[h].y],e[h].v);
					f[e[h].y][tmp]=f[tmp][e[h].y];
				}
				added++;flag=1;
			}
			if(flag){
				up(k,1,N)if(C[k]<=ask[i].c)up(m,1,N)up(n,1,N)
				if(f[m][k]+f[k][n]<f[n][m])f[n][m]=f[m][k]+f[n][k];
			}
			up(j,1,N)if(f[now][j]<=ask[i].d&&now!=j)cnt[j]=i;
			up(j,1,N)if(cnt[j]==i&&j!=now)ask[i].ans++;
		}
	}
	void output(){
		sort(ask+1,ask+Q+1,cmp3);
		up(i,1,Q)printf("%d\n",ask[i].ans);
		//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	init();
	slove();
	output();
	return 0;
}