记录编号	59428	评测结果	AAAAA
题目名称	[NOI 1998]SERNET模拟	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2013-05-06 21:21:28	内存使用	0.51 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<deque>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int SIZEN=101,INF=0x7fffffff/2;
const int SIZEP=10001;
//下标是1~n
int n,m,k,test;
int c[SIZEN][SIZEN]={0};
int leng[SIZEN][SIZEN]={0};
int maxl[SIZEN]={0};//每个点连出的最长边
int lis[SIZEN]={0};
class PACK{
public:
	int t;
	int source,goal;
	PACK(){t=source=goal=0;}
}p[SIZEP];
int S,T;
void floyd(void){
	int i,j,k;
	for(k=1;k<=n;k++){
		if(k==S||k==T) continue;
		for(i=1;i<=n;i++){
			if(i==T) continue;
			for(j=1;j<=n;j++){
				if(j==S) continue;
				leng[i][j]=min(leng[i][j],leng[i][k]+leng[k][j]);
			}
		}
	}
}
void read(void){
	int i,j;
	int a,b,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		for(j=1;j<i;j++) c[i][j]=c[j][i]=INF;
	}
	for(i=1;i<=n;i++){
		scanf("%d",&a);
		lis[a]=i;
	}
	scanf("%d",&m);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&t);
		c[lis[a]][lis[b]]=c[lis[b]][lis[a]]=t;
	}
	scanf("%d",&k);
	for(i=1;i<=k;i++){
		scanf("%d%d%d%d",&a,&p[i].t,&p[i].source,&p[i].goal);
		p[i].source=lis[p[i].source],p[i].goal=lis[p[i].goal];
	}
	scanf("%d",&test);//测试的时刻
}
void getmaxl(void){
	int i,j,nowmax;
	for(i=1;i<=n;i++){
		nowmax=-1;
		for(j=1;j<=n;j++){
			if(c[i][j]!=INF) nowmax=max(nowmax,c[i][j]);
		}
		maxl[i]=nowmax;
	}
}
#define now p[x]
int final(int x){//数据包x最终延续到的时间
	int ans=-1;
	int i,n1,n2;
	for(i=1;i<=n;i++){
		n1=leng[now.source][i];
		n2=(i==now.goal)?0:maxl[i];
		if(n1!=INF) ans=max(ans,n1+n2);
	}
	return now.t+ans;
}
bool check(int x){//数据包x是否在时刻test存在于网络中
	return final(x)>test;
}
void slove(void){
	int ans=0;
	int i,j,x;
	for(x=1;x<=k;x++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				leng[i][j]=c[i][j];
			}
		}
		S=p[x].source,T=p[x].goal;
		floyd();
		if(check(x)) ans++;
	}
	printf("%d\n",ans);
}
int main(){
	freopen("sernet.in","r",stdin);
	freopen("sernet.out","w",stdout);
	read();
	getmaxl();
	slove();
	return 0;
}