使用dijkstra算法可以在n^2logm 时间复杂度内计算出任意两点之间的最短路径，这题关键在于枚举每条边(a,b)使其免费，每个路径的start到end的最小值，因为使一条边免费最短路可能发生变化，其应该为：
#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define fi first #define se second typedef long long ll; using namespace std; const int N = 1000 + 5; const ll INF = 1e18; vector<pair<int,int> > g[N]; int n,m,k; bool vis[N]; ll dis[N]; ll d[N][N]; void dijkstra(int st){ for(int i = 1;i <= n;i++){ dis[i] = INF; vis[i] = 0; } priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > q; q.push(mp(0LL,st)); dis[st] = 0; while(!q.empty()){ pair<ll,int> p = q.top(); q.pop(); int u = p.se; ll dist = p.fi; if(vis[u])continue; vis[u] = 1; for(int i = 0;i < g[u].size();i++){ int v = g[u][i].fi,w = g[u][i].se; if(dis[v] > dist + w){ dis[v] = dist + w; q.push(mp(dis[v],v)); } } } for(int i = 1;i <= n;i++) d[st][i] = dis[i]; } vector<pair<int,int> > e,e1; int main(){ cin>>n>>m>>k; for(int i = 1;i <= m;i++){ int u,v,w; cin>>u>>v>>w; g[u].pb(mp(v,w)); g[v].pb(mp(u,w)); e.pb(mp(u,v)); } for(int i = 1;i <= n;i++) dijkstra(i); //cout<<"OK"<<endl; for(int i = 1;i <= k;i++){ int u,v; cin>>u>>v; e1.pb(mp(u,v)); } ll tot = INF; for(auto edge:e){ ll tmp = 0; int a = edge.fi,b = edge.se; for(auto path:e1){ int st = path.fi,ed = path.se; ll minn = min(d[st][ed],min(d[st][a] + d[b][ed],d[st][b] + d[a][ed])); tmp += minn; } tot = min(tot,tmp); } cout<<tot<<endl; return 0; }