https://codeforces.com/contest/1433/problem/G
思路：开始看到了路线免费，以为是出了分层最短路板子，看了看发现只让一条路免费。
开始直接考虑暴力，枚举每条边，然后每个点进行dijkstra，最后取最小。复杂度O(n^2klogm);
考虑一下对每个点其实可以先预处理，提前处理好每个点的对应的最短路。O(n^2logm)
考虑免费的边的贡献。
对每一个ki来说，边(a,b)有三种情况。
1.开始不在其最短路路径上，免费后也不在其最短路路径上。
2.开始不在其最短路路径上，免费后在其最短路路径上。
3.开始在其最短路路径上，免费后在其最短路路径上。
对于第一种情况，ki的最短路长度不变，仍然是原来的dis[ki.first][ki.second] （ki.first和ki.second分别代表其起点和终点)
对于第二三种情况，ki的最短路长度可能变化,dis[ki.first][a]+dis[ki.second][b];dis[ki.first][b]+dis[ki.second][a];
那么枚举边,再枚举每个k,求出总和的最小.
总时间复杂度O（mk+n^2logm）
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=1e3+100; typedef long long LL; typedef pair<LL,LL>P;///first距离,second编号 LL dis[maxn]; LL n,m,k,start; struct edge{ LL to,cost; }; vector<edge>g[maxn]; LL f[maxn][maxn]; bool vis[maxn]; void dijkstra() { LL s=start; memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; priority_queue< P, vector<P>, greater<P> >que; que.push({0,s}); while(!que.empty()) { P p=que.top();que.pop(); LL v=p.second; if(vis[v]) continue; vis[v]=1; for(LL i=0;i<g[v].size();i++) { edge e=g[v][i]; if(dis[e.to]>dis[v]+e.cost) { dis[e.to]=dis[v]+e.cost; que.push({dis[e.to],e.to}); } } } for(LL j=1;j<=n;j++){ f[s][j]=dis[j]; } } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); cin>>n>>m>>k; vector<pair<LL,LL> >Edge; for(LL i=1;i<=m;i++) { LL u,v,w;cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); Edge.push_back({u,v}); } vector<pair<LL,LL>> v; for(LL i=1;i<=k;i++) { LL a,b;cin>>a>>b; v.push_back({a,b}); } for(LL i=1;i<=n;i++) { start=i; dijkstra(); } LL sum=1e18; for(auto i:Edge)///遍历每条边 { LL a=i.first;LL b=i.second; LL ans=0; for(auto j:v)///遍历所有人 { ans+=min( f[j.first][j.second],min(f[j.first][a]+f[j.second][b],f[j.first][b]+f[j.second][a]) ); } sum=min(sum,ans); } cout<<sum<<endl; return 0; }
