题目链接

题目描述

有 个路口与 条单向道路（均为单行道）， 号路口为邮局， 号路口各有一件包裹待投递。邮递员一次只能携带一件包裹，每次需从邮局取件出发，将包裹送达目的地后必须返回邮局，方可取下一件。已知任意两点间互相可达，求完成全部 件投递并最终回到邮局所需的最短总时间。

解题思路

  • 对每个目的地 ，本次往返的最短时间为“邮局到 的最短路”与“ 回邮局的最短路”之和。
  • 记 为从 号点到 的最短路距离；将图反向后，再求从 出发的最短路，得到 为从 到 的最短路距离（在原图中）。
  • 答案为
  • 因边权为非负整数，采用堆优化 Dijkstra，分别在正图与反图各跑一次即可。

代码

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

static const long long INF = (1LL<<62);

// Dijkstra：从源点 s 出发，返回 dist 数组
static vector<long long> dijkstra(int n, const vector<vector<pair<int,int>>>& g, int s) {
    vector<long long> dist(n + 1, INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
    dist[s] = 0; pq.push({0, s});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : g[u]) {
            long long nd = d + w;
            if (nd < dist[v]) { dist[v] = nd; pq.push({nd, v}); }
        }
    }
    return dist;
}

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<pair<int,int>>> g(n + 1), gr(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        gr[v].push_back({u, w});
    }

    auto d_to = dijkstra(n, g, 1);
    auto d_from = dijkstra(n, gr, 1); // 反图上从 1 出发 => 原图上到 1 的最短路

    long long ans = 0;
    for (int v = 2; v <= n; ++v) ans += d_to[v] + d_from[v];
    cout << ans << '\n';
    return 0;
}

import java.util.*;

public class Main {
    static final long INF = 1L << 62;

    static long[] dijkstra(int n, List<int[]>[] g, int s) {
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        dist[s] = 0; pq.add(new long[]{0L, s});
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long d = cur[0]; int u = (int)cur[1];
            if (d != dist[u]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                long nd = d + w;
                if (nd < dist[v]) { dist[v] = nd; pq.add(new long[]{nd, v}); }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<int[]>[] g = new ArrayList[n + 1];
        List<int[]>[] gr = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) { g[i] = new ArrayList<>(); gr[i] = new ArrayList<>(); }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
            g[u].add(new int[]{v, w});
            gr[v].add(new int[]{u, w});
        }
        long[] dTo = dijkstra(n, g, 1);
        long[] dFrom = dijkstra(n, gr, 1);
        long ans = 0;
        for (int v = 2; v <= n; v++) ans += dTo[v] + dFrom[v];
        System.out.println(ans);
    }
}

import heapq

def dijkstra(n: int, g: list[list[tuple[int,int]]], s: int) -> list[int]:
    INF = 1 << 62
    dist = [INF] * (n + 1)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
gr = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
    gr[v].append((u, w))

d_to = dijkstra(n, g, 1)
d_from = dijkstra(n, gr, 1)
ans = 0
for v in range(2, n + 1):
    ans += d_to[v] + d_from[v]
print(ans)

算法及复杂度

  • 算法：两次 Dijkstra。一次在原图求 ，一次在反图求 ，并累加 。
  • 时间复杂度：。
  • 空间复杂度：。