官方题解｜道路削减

题目解析

令 $D_i$ 为从城市 $1$ 到城市 $i$ 的最短距离。无论选择哪些道路，显然有 $d_i\geq D_i$。
所以如果有选择道路的方案使得 $d_i=D_i$ 成立，那么这就是最优解。事实上，这样的选择方法总是存在的。

对于每个 $i=2,3,\ldots,N$，只需保留 “从城市 $1$ 到城市 $i$ 的最短路径中的最后一条道路” 即可。

答案可以通过记录 $\tt{Dijkstra}$ 算法中到达每个城市前的最后一条道路来找到。

AC代码

C++ AC代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5;

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::tuple<int, int, int>> g[N + 1];
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        g[u].emplace_back(v, w, i);
        g[v].emplace_back(u, w, i);
    }
    std::priority_queue<std::pair<i64, int>,
        std::vector<std::pair<i64, int>>,
            std::greater<std::pair<i64, int>>> pq;
    std::vector<i64> dist(n + 1, i64(1e15));
    std::vector<int> path(n + 1);
    pq.emplace(0, 1);
    dist[1] = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (dist[u] < d) continue;
        for (auto &[v, w, i] : g[u]) {
            if (dist[v] <= d + w) continue;
            dist[v] = d + w;
            path[v] = i;
            pq.emplace(d + w, v);
        }
    }
    for (int i = 2; i <= n; ++i)
        std::cout << path[i] << " \n"[i == n];
    return 0;
}

Python AC代码：

import heapq
n, m = map(int, input().split())
g = [[] for i in range(n + 1)]
for i in range(1, m + 1):
    u, v, w = map(int, input().split())
    g[u].append((v, w, i))
    g[v].append((u, w, i))
pq = [[0, 1]]
heapq.heapify(pq)
dist = [10**15] * (n + 1)
path = [0] * (n + 1)
dist[1] = 0
while pq:
    d, u = heapq.heappop(pq)
    if dist[u] < d:
        continue
    for v, w, i in g[u]:
        if dist[v] <= d + w:
            continue
        dist[v] = d + w
        path[v] = i
        heapq.heappush(pq, (d + w, v))
print(" ".join(map(str, path[2:])))

复杂度分析

使用 $\tt{Dijkstra}$ 算法求最短路，并在过程中记录路径，时间复杂度为 $\mathrm{O}(M \log{M})$。