codeforces 1433G

题目链接：https://codeforces.com/problemset/problem/1433/G

首先跑 (n) 遍最短路，处理出所有点对之间的最短路
然后考虑枚举边，对于每一条边，可能对(a[i],b[i])之间的最短路径有影响，也有可能没影响，取最小值即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int maxn = 1010;
const ll INF = (1ll << 58ll);

int n,m,k;
int dis[maxn][maxn],u[maxn],v[maxn],a[maxn],b[maxn];

priority_queue<P,vector<P>,greater<P> > q;

int h[maxn],cnt = 0;
struct E{
	int to,next,cost;
}e[maxn << 1];
void add(int u,int v,int w){
	e[++cnt].to = v;
	e[cnt].cost = w;
	e[cnt].next = h[u];
	h[u] = cnt;
}

void dij(int s){
	while(!q.empty()) q.pop();
	dis[s][s] = 0;
	
	q.push(P(0,s));
	
	while(!q.empty()){
		P p = q.top(); q.pop();
		int u = p.second;
		if(p.first > dis[s][u]) continue; // 之前被更新过了 
		for(int i=h[u];i!=-1;i=e[i].next){
			int v = e[i].to, w = e[i].cost;
			if(dis[s][v] > dis[s][u] + w){
				dis[s][v] = dis[s][u] + w;
				q.push(P(dis[s][v],v));
			}
		}
	} 
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	memset(dis,0x3f,sizeof(dis));
	memset(h,-1,sizeof(h));
	n = read(), m = read(), k = read();
	
	int w;
	for(int i=1;i<=m;++i){
		u[i] = read(), v[i] = read(), w = read();
		add(u[i],v[i],w), add(v[i],u[i],w);
	} 
	
	for(int i=1;i<=n;++i){
		dij(i);
	}
	
	for(int i=1;i<=k;++i){ a[i] = read(), b[i] = read(); }
	
	ll ans = INF;
	for(int i=1;i<=m;++i){
		ll res = 0;
		for(int j=1;j<=k;++j){
			res += min(min(dis[a[j]][b[j]],dis[a[j]][u[i]] + dis[b[j]][v[i]]),dis[a[j]][v[i]] + dis[b[j]][u[i]]);
		}
		ans = min(ans, res);
	}
	
	printf("%lld
",ans);
	
	return 0;
}