记录编号	575539	评测结果	AAAAA
题目名称	[NOI 1998]SERNET模拟	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2022-09-21 12:58:52	内存使用	1.19 MiB

#include<bits/stdc++.h>
const int N=101,K=10001,INF=0x3F3F3F3F;
using namespace std;
struct packet
{//数据包
	int id,s,t,stime;
}P[K];
int n,m,k,s,t,dia,T,ans;
int mapping[N],g[N][N],dis[N][N],farest[N];

void floyd()
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			dis[i][j] = g[i][j];
	for (int k=1;k<=n;k++)//求i~j最短路
	{//阶段：中间点集合 1~k
		//s~t 中间点集合不包含s,t
		if (k==s || k==t) continue;
		for (int i=1;i<=n;i++)
		{
			if (i==t) continue;
			for (int j=1;j<=n;j++)
			{
				if (j==s) continue;
				if (dis[i][k]+dis[k][j]<dis[i][j])
					dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
	for (int j=1;j<=n;j++)//求数据包从s到j最长传输时间
		if (s!=j && s!=t && dis[s][j]!=INF)
		{
			int maxe=farest[j];//j最长出边
			if (j==t) maxe=0;//终点不再群发
			if (dis[s][j] + maxe > dia)
				dia=dis[s][j] + maxe;//更新最长传输时间
		}
}

int main()
{
	freopen("sernet.in","r",stdin);
	freopen("sernet.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int num;
		scanf("%d",&num);
		mapping[num]=i;//将编号映射到1~n
		for (int j=1;j<=n;j++)	g[i][j]=INF;
		g[i][i]=0;
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		a=mapping[a]; b=mapping[b];
		if (v>farest[a]) farest[a]=v;//a最长出边
		if (v>farest[b]) farest[b]=v;
		g[a][b] = g[b][a] = v;//边权
	}
	scanf("%d",&k);
	for (int i=1;i<=k;i++)
		scanf("%d%d%d%d",&P[i].id,&P[i].stime,&P[i].s,&P[i].t);
	scanf("%d",&T);
	
	for (int i=1;i<=k;i++)
	{
		s=mapping[P[i].s]; t=mapping[P[i].t];
		dia=0;
		floyd();
		int last=dia + P[i].stime;//持续到的时刻=开始传输时刻+最大传输时长
		if (last>T) ans++;
	}
	
	printf("%d\n",ans);
	return 0;
}