题目链接

邮递员送信

题目描述

在一个有 个路口和 条单向道路的城市里，1 号路口是邮局。邮递员需要向 2 号到 号路口的每一个路口都投递一件包裹。

投递规则如下：

  • 邮递员一次只能携带一件包裹。
  • 每次都必须从 1 号路口（邮局）出发，前往目的地路口。
  • 送达后，必须返回 1 号路口（邮局），才能取下一件包裹。

你需要计算，邮递员完成所有 件包裹的投递并最终回到邮局，所需的最短总时间。

解题思路

这道题的核心是计算 次独立的投递任务的总耗时。

1. 分解问题

对于每一个目的地 （从 2 到 ），邮递员都需要完成一次往返行程：

  • 从邮局（1号路口）出发，到达目的地 。
  • 从目的地 出发，返回邮局（1号路口）。

完成对路口 的投递所需的最短时间，就是 从 1 到 的最短路径长度 加上 从 到 1 的最短路径长度。

总的最短时间就是将所有目的地（2 到 ）的往返最短时间相加：

2. 求解所有最短路径

问题转化为了如何高效地计算 shortest_path(1, i) 和 shortest_path(i, 1)。

  • 计算 shortest_path(1, i)： 这是一个典型的单源最短路径问题。由于所有道路耗时（边权）都是非负的，我们可以从源点 1 出发，运行一次 Dijkstra 算法，这样就能得到 1 号路口到所有其他路口的最短路径长度。

  • 计算 shortest_path(i, 1)： 这是从所有路口 到单个汇点 1 的最短路径问题。如果为每个 都运行一次 Dijkstra，效率会很低。 这里有一个非常巧妙的技巧：反向图 (Reversed/Transposed Graph)。

    • 我们构建一个原图的反向图 G_rev。如果在原图 G 中有一条从 到 的边，我们就在 G_rev 中添加一条从 到 的边，权重不变。
    • 这样做之后，在原图 G 中从 到 1 的最短路径，就等价于在反向图 G_rev 中从 1 到 的最短路径。
    • 因此，我们只需要在反向图上，再次以 1 为源点运行一次 Dijkstra 算法，就能求出所有路口到 1 号路口的最短路径长度。

算法整体流程

  1. 读取图的结构，同时构建邻接表 adj 和反向邻接表 adj_rev。
  2. 以 1 为源点，在 adj (正向图) 上运行一次 Dijkstra 算法，得到 dist_from_1 数组，存储 1 到各点的最短路。
  3. 以 1 为源点，在 adj_rev (反向图) 上运行一次 Dijkstra 算法，得到 dist_to_1 数组，存储各点到 1 的最短路。
  4. 遍历从 2 到 的所有路口 ，累加 dist_from_1[i] + dist_to_1[i]，得到最终答案。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    int weight;
};

struct Node {
    int id;
    long long dist;

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

void dijkstra(int n, int start_node, const vector<vector<Edge>>& adj, vector<long long>& dist) {
    dist.assign(n + 1, INF);
    dist[start_node] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({start_node, 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        int u = current.id;
        long long d = current.dist;

        if (d > dist[u]) {
            continue;
        }

        for (const auto& edge : adj[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.push({edge.to, dist[edge.to]});
            }
        }
    }
}

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

    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> adj(n + 1);
    vector<vector<Edge>> adj_rev(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj_rev[v].push_back({u, w});
    }

    vector<long long> dist_from_1;
    vector<long long> dist_to_1;

    dijkstra(n, 1, adj, dist_from_1);
    dijkstra(n, 1, adj_rev, dist_to_1);

    long long total_time = 0;
    for (int i = 2; i <= n; ++i) {
        total_time += dist_from_1[i] + dist_to_1[i];
    }

    cout << total_time << endl;

    return 0;
}

import java.util.*;

class Main {
    static final long INF = Long.MAX_VALUE;

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class Node implements Comparable<Node> {
        int id;
        long dist;

        Node(int id, long dist) {
            this.id = id;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node other) {
            return Long.compare(this.dist, other.dist);
        }
    }
    
    public static long[] dijkstra(int n, int startNode, List<List<Edge>> adj) {
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[startNode] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(startNode, 0));
        
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.id;
            long d = current.dist;
            
            if (d > dist[u]) {
                continue;
            }
            
            for (Edge edge : adj.get(u)) {
                if (dist[u] != INF && dist[u] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[u] + edge.weight;
                    pq.add(new Node(edge.to, dist[edge.to]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<List<Edge>> adj = new ArrayList<>();
        List<List<Edge>> adjRev = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
            adjRev.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adj.get(u).add(new Edge(v, w));
            adjRev.get(v).add(new Edge(u, w));
        }

        long[] distFrom1 = dijkstra(n, 1, adj);
        long[] distTo1 = dijkstra(n, 1, adjRev);

        long totalTime = 0;
        for (int i = 2; i <= n; i++) {
            totalTime += distFrom1[i] + distTo1[i];
        }

        System.out.println(totalTime);
    }
}

import heapq

def dijkstra(n, start_node, adj):
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[start_node] = 0
    pq = [(0, start_node)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, w in adj.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
                
    return dist

def main():
    n, m = map(int, input().split())
    
    adj = {}
    adj_rev = {}
    for _ in range(m):
        u, v, w = map(int, input().split())
        if u not in adj: adj[u] = []
        if v not in adj_rev: adj_rev[v] = []
        adj[u].append((v, w))
        adj_rev[v].append((u, w))
        
    dist_from_1 = dijkstra(n, 1, adj)
    dist_to_1 = dijkstra(n, 1, adj_rev)
    
    total_time = 0
    for i in range(2, n + 1):
        total_time += dist_from_1[i] + dist_to_1[i]
        
    print(total_time)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：Dijkstra 算法
  • 时间复杂度：。我们运行了两次堆优化的 Dijkstra 算法，每次的复杂度为 。最后累加结果的复杂度为 。因此，总时间复杂度由 Dijkstra 算法主导。
  • 空间复杂度：。用于存储正向和反向图的邻接表，以及 Dijkstra 算法所需的距离数组和优先队列。