【題解】Codeforces 1433G. Reducing Delivery Cost

【題目敘述】https://codeforces.com/contest/1433/problem/G

#include <bits/stdc++.h>
using namespace std;

int n, m, k, dis[1005][1005], a[1005], b[1005];
vector <pair<int, int> > v[1005], e;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0, c, d, w; i < m; i++){
        cin >> c >> d >> w;
        v[c].push_back({d, w});
        v[d].push_back({c, w});
        e.push_back({c, d});
    }
    memset(dis, -1, sizeof(dis));
    for (int s = 1; s <= n; s++){
        dis[s][s] = 0;
        priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
        pq.push({0, s});
        while (!pq.empty()){
            int x = pq.top().second, y = pq.top().first;
            pq.pop();
            if (dis[s][x] != y) continue;
            for (auto i:v[x]){
                if (dis[s][i.first] == -1 || dis[s][i.first] > dis[s][x]+i.second){
                    dis[s][i.first] = dis[s][x]+i.second;
                    pq.push({dis[s][i.first], i.first});
                }
            }
        }
    }
    for (int i = 0; i < k; i++){
        cin >> a[i] >> b[i];
    }
    int ans = 1e9;
    for (auto [x, y]:e){
        int tot = 0;
        for (int i = 0; i < k; i++){
            tot += min(dis[a[i]][b[i]], min(dis[a[i]][x]+dis[y][b[i]], dis[a[i]][y]+dis[x][b[i]]));
        }
        ans = min(ans, tot);
    }
    cout << ans << "\n";
}
分享本文 Share with friends