G. Reducing Delivery Cost

题意

一个1000点，1000条边的通联图，你可以令一条边权值为0，然后使得之后的1000条s到e的最短路总和最小。

解法

对每个点求一个到其他所有点的最短路，然后枚举每条边a，b。
s到e的最短路就是
ps: 自己对每条路进行标记，然后跑最短路的时候，就不经过这条边，然后这条边两个端点去找其他点的最短路，但是WA5了。。。

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define deubg_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------

int N,M,K; 
int h[maxn],e[maxn],w[maxn],ne[maxn],idx = 1;
bool vis[2010];
int dis[1010][1010];
struct Road{
    int x,y;
}road[1010];
struct Line{
    int x,y;
}line[1010];
struct node{
    int u,w;
    bool operator <(const node& o)const{
        return w > o.w;
    }  
};
priority_queue<node> q;
void add(int a,int b,int c){
    e[++idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}
void dij(int s,int d[]){
    for(int i = 1;i<=N;i++) d[i] = inf;
    for(int i = 1;i<=N;i++) vis[i] = 0;
    d[s] = 0;
    q.push({s,d[s]});

    while(q.size()){
        node cur = q.top();q.pop();
        int u = cur.u;
        if(vis[u]) continue;
        vis[u] = 1;

        for(int i = h[u];i;i = ne[i]){
            int v = e[i];
            if(d[u] + w[i] < d[v]){
                d[v] = d[u] + w[i];
                q.push({v,d[v]});
            }
        }
    }
}
void solve(){
    int ans = 2e9;
    for(int i = 1;i<=M;i++){
        int cur_ans = 0;
        int a = road[i].x,b = road[i].y;
        for(int j = 1;j<=K;j++){
            int x = line[j].x, y = line[j].y;
            cur_ans += min(dis[x][y],min(dis[a][x] + dis[b][y],dis[b][x] + dis[a][y]));
        }
        ans = min(ans,cur_ans);
    }
    printf("%d\n",ans);
}
int main(){
//    debug_in;

    read(N,M,K);
    for(int i = 1;i<=M;i++){
        int a,b,c;read(a,b,c);
        add(a,b,c);
        add(b,a,c);
        road[i] = {a,b};
    }
    for(int i = 1;i<=K;i++) read(line[i].x,line[i].y);
    for(int i = 1;i<=N;i++){
        dij(i,dis[i]);
    }
    solve();
    return 0;
}