CF1433 G.Reducing Delivery Cost【最短路】

题目链接：codeforces 1433G

题解

首先预处理在没有免费边情况下的最短路，再暴力枚举边即可。

假设当先线路为 j，对于边 (a, b) ，它有两种情况：

  1. 免费后不在最短路上，结果是 f[j.first][j.second]。
  2. 免费后在最短路上，因为这条边的价值改变了，可能最短路会变，所以要讨论，结果是 min(f[j.second][a]+f[j.first][b], f[j.first][a]+f[j.second][b])。

时间复杂度为 。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
typedef long  long ll;
typedef pair<ll, ll> PII;
const int N = 1010;
int n, m, k, sta;
struct Edge {
    int v, w;
};
vector<Edge> g[N];
bool vis[N];
int dis[N];
int f[N][N];
void dijstra() {
    int s = sta;
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({dis[s], s});
    while (!q.empty()) {
        PII e = q.top(); q.pop();
        int v = e.second;
        if (vis[v]) continue;
        vis[v] = 1;
        for (int i = 0; i < g[v].size(); i++) {
            Edge e = g[v][i];
            if (dis[e.v] > dis[v] + e.w) {
                dis[e.v] = dis[v] + e.w;
                q.push({dis[e.v], e.v});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        f[s][i] = dis[i];
    }
}
int main() {
    cin >> n >> m >> k;
    vector<PII> edge;
    for (int i = 1; i <= m; i++) {
        int 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<PII> v;
    for (int i = 1; i <= k; i++) {
        int a, b; cin >> a >> b;
        v.push_back({a ,b});
    }
    for (int i = 1; i <= n; i++) {
        sta = i;
        dijstra();
    }
    int sum = 0x3f3f3f3f;
    for (auto i : edge) {
        int a = i.first, b = i.second;
        int ans = 0;
        for (auto j : v) {
            ans += min(f[j.first][j.second], min(f[j.first][a] + f[j.second][b], f[j.second][a] + f[j.first][b]));
        }
        sum = min(ans, sum);
    }
    cout << sum << endl;
    return 0;
}