记录编号	575588	评测结果	AAAAA
题目名称	[NOI 1998]SERNET模拟	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2022-09-21 21:38:31	内存使用	1.16 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=100+5;
const int inf=0x3f3f3f3f;
int n,m,q;
int id[N],mp[N][N],tmp[N][N],mx[N]={0};
int p[10*N]={0};
int main(){
	freopen ("sernet.in","r",stdin);
	freopen ("sernet.out","w",stdout);
	scanf("%d",&n);
	memset(mp,0x3f,sizeof(mp));
	for (int i=1;i<=n;i++)scanf("%d",&m),id[m]=i,mp[i][i]=0;
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
	    int x,y,t;scanf("%d%d%d",&x,&y,&t);
	    x=id[x];y=id[y];
	    mp[x][y]=mp[y][x]=t;
	    mx[x]=max(mx[x],t);mx[y]=max(mx[y],t);
    }
    scanf("%d",&q);
    for (int tt=1;tt<=q;tt++){
        int a,b,x,y;scanf("%d%d%d%d",&a,&b,&x,&y);
        int now=0;x=id[x];y=id[y];
        memcpy(tmp,mp,sizeof(tmp));
        for (int k=1;k<=n;k++){
            if (k==x||k==y)continue;
            for (int i=1;i<=n;i++){
                for (int j=1;j<=n;j++){
                    if (tmp[i][k]!=inf&&tmp[k][j]!=inf){
                        tmp[i][j]=min(tmp[i][j],tmp[i][k]+tmp[k][j]);
                    }
                }
            }
        }
        for (int i=1;i<=n;i++)if (tmp[x][i]!=inf)now=max(now,tmp[x][i]+(i!=y)*mx[i]);
        p[tt]=b+now;
    }
    int s,ans=0;scanf("%d",&s);
    for (int i=1;i<=q;i++)if (p[i]>s)ans++;
    printf("%d\n",ans);
    return 0;
}