玛丽卡

题意

给你一张无向带权图，起点是 1，终点是 N。

现在有一条路会因为维修而完全不能走，但不知道具体是哪一条。
题目保证：无论封掉哪条边，从 1 仍然能到 N。

玛丽卡会在剩下的边里重新走最短路。
要求输出最糟糕情况下，这条最短路会变成多长。

样例直觉图

这张图展示了“封掉原最短路上的一条边后，被迫绕路”的现象：

graph G {
  rankdir=LR;
  1 -- 2 [label="8"];
  2 -- 5 [label="1", color="red", penwidth=2];
  2 -- 3 [label="9"];
  3 -- 5 [label="10"];
}

如果红边 2-5 被封掉，原来的最短路就失效了，只能走更长的替代路线。
所以关键不在“封哪条边”，而在“哪些边真的有能力把当前最短路挤掉”。

思路

先看一个最直接的小数据暴力：

cpp

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
71
72
73
74
75#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const long long INF = (1LL << 60);

int n, m;
int eu[1005], ev[1005];
long long ew[1005];
long long dist_arr[MAXN][MAXN];
long long backup_dist[MAXN][MAXN];

void floyd(long long a[MAXN][MAXN]) {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][k] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= n; j++) {
                if (a[k][j] >= INF / 2) {
                    continue;
                }
                long long nd = a[i][k] + a[k][j];
                if (nd < a[i][j]) {
                    a[i][j] = nd;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                backup_dist[i][j] = 0;
            }
            else {
                backup_dist[i][j] = INF;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i] >> ew[i];
        backup_dist[eu[i]][ev[i]] = ew[i];
        backup_dist[ev[i]][eu[i]] = ew[i];
    }

    long long answer = 0;

    // 暴力枚举哪条边被封掉，然后重跑一次 Floyd。
    for (int ban = 1; ban <= m; ban++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist_arr[i][j] = backup_dist[i][j];
            }
        }

        dist_arr[eu[ban]][ev[ban]] = INF;
        dist_arr[ev[ban]][eu[ban]] = INF;

        floyd(dist_arr);
        answer = max(answer, dist_arr[1][n]);
    }

    cout << answer << '\n';

    return 0;
}

暴力做法就是：

枚举每一条边
把它临时删掉
重算 1 -> N 的最短路
取这些最短路里的最大值

这个做法最贴题意，但把所有边都删一遍没有必要。

关键观察和 P2176 很像：

如果某条边不在我们当前求出的一条最短路上
那么把它封掉之后，这条最短路本身仍然完整存在

既然原来的这条最短路还在，那么新的最短路长度就不可能变大。
所以只有一类边值得枚举：

某条已知最短路上的边

于是正式做法变成：

第一次 Dijkstra，求出从 1 到 N 的一条最短路
记录每个点的前驱点和前驱边
从 N 倒着回溯，恢复出这条最短路上的所有边编号
依次禁用这些边，再跑一次 Dijkstra
取得到的最短路长度最大值

和代码的对应关系：

parent_node、parent_edge：第一次最短路时记录路径
path_edges：回溯出的那条最短路
banned_id：当前被封掉的边
dijkstra(1, false, banned_id)：忽略这条边重新算最短路

代码

cpp

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000 + 5;
const int MAXM = 20000 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m;
int eu[MAXM], ev[MAXM];
long long ew[MAXM];

int head[MAXN], to[MAXM * 2], nxt[MAXM * 2], edge_id[MAXM * 2], edge_cnt;
long long dist_arr[MAXN];
bool vis[MAXN];
int parent_node[MAXN], parent_edge[MAXN];

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
    }
}

void add_edge(int u, int v, int id) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_id[edge_cnt] = id;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void dijkstra(int start, bool save_parent, int banned_id) {
    for (int i = 1; i <= n; i++) {
        dist_arr[i] = INF;
        vis[i] = false;
        if (save_parent) {
            parent_node[i] = 0;
            parent_edge[i] = 0;
        }
    }

    priority_queue<HeapNode> pq;
    dist_arr[start] = 0;
    pq.push({start, 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int id = edge_id[i];
            if (id == banned_id) {
                continue;
            }

            int v = to[i];
            long long nd = dist_arr[u] + ew[id];
            if (nd < dist_arr[v]) {
                dist_arr[v] = nd;
                if (save_parent) {
                    parent_node[v] = u;
                    parent_edge[v] = id;
                }
                pq.push({v, nd});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init_graph();

    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i] >> ew[i];
        add_edge(eu[i], ev[i], i);
        add_edge(ev[i], eu[i], i);
    }

    dijkstra(1, true, 0);

    vector<int> path_edges;
    int cur = n;
    while (cur != 1) {
        path_edges.push_back(parent_edge[cur]);
        cur = parent_node[cur];
    }

    long long answer = 0;

    // 只有这条已知最短路上的边被封掉，才可能让最短路变长。
    for (size_t i = 0; i < path_edges.size(); i++) {
        int banned_id = path_edges[i];
        dijkstra(1, false, banned_id);
        answer = max(answer, dist_arr[n]);
    }

    cout << answer << '\n';

    return 0;
}

复杂度

设回溯出的这条最短路有 L 条边。

第一次 Dijkstra：

$O(M log N)$

之后最多再跑 L 次 Dijkstra，而 L <= N-1，所以总复杂度是：

$O(N * M log N)$

空间复杂度：

$O(N + M)$

总结

这题的核心不是“删边后重跑最短路”，而是先缩小枚举范围。

只要想清楚：

不在某条已知最短路上的边，被删掉后不可能让答案变差

那么就只需要关心那条最短路上的边，后面的实现就是标准的：

路径恢复
枚举删边
重跑 Dijkstra

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

样例直觉图

思路

代码

复杂度

总结

一图流解析