https://codeforces.com/contest/1433/problem/G
998ms卡过去了。。。
n^3floyed跑出来每个点到另一个点的答案
然后枚举删除每条边，再枚举每个route，可以O(1)找到此时这个route的最小代价，加起来得到删掉这条边的答案,复杂度为O(mk)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=1010; const int inf=1e9+10; int n,m,k,cnt,tot,cas,ans; int f[maxl][maxl]; struct edge { int u,v,w; }edg[maxl*maxl]; struct ed { int v,l; }; struct route { int a,b; }a[maxl]; vector<ed> e[maxl]; bool vis[maxl][maxl]; char s[maxl]; inline void prework() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=inf; for(int i=1;i<=n;i++) f[i][i]=0; int u,v,w; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); edg[i]=edge{u,v,w}; f[u][v]=f[v][u]=min(f[u][v],w); } for(register int k=1;k<=n;++k) for(register int i=1;i<=n;++i) if(k!=i) for(register int j=1;j<=n;++j) if(j!=i && k!=j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); for(int i=1;i<=k;i++) scanf("%d%d",&a[i].a,&a[i].b); } inline void mainwork() { int u,v,tmp;ans=inf; for(register int i=1;i<=m;++i) { u=edg[i].u;v=edg[i].v; tmp=0; for(register int j=1;j<=k;++j) tmp+=min(f[a[j].a][a[j].b],min(f[a[j].a][u]+f[a[j].b][v],f[a[j].a][v]+f[a[j].b][u])); ans=min(ans,tmp); } } inline void print() { printf("%d",ans); } int main() { int t=1; //scanf("%d",&t); for(cas=1;cas<=t;cas++) { prework(); mainwork(); print(); } return 0; }
