M30910: 邮递员送快递

Dijkstra, http://cs101.openjudge.cn/practice/30910/

某县有n个村庄，由一个邮递员负责送快递。村庄编号1到n。邮局在村庄 1。他总共要送 n-1 样东西，其目的地分别是村庄 2 到村庄 n。由于这个县地方小且交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路，每条道路直接连接两个村庄。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1 样东西并且最终回到邮局最少需要的时间。
输入
第一行包括两个整数，n 和 m，表示村庄的村庄数量和道路数量。(n 不超过 1100,m 不超过 100000）
接下来的m行，每行三个整数，u,v,w，表示从村庄 u 到村庄 v 有一条通过时间为 w 的道路
输出
输出仅一行，包含一个整数，为最少需要的时间。
样例输入
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
样例输出
83

思路：从邮局（村庄 1）出发，需要到村庄 2..n 各送一次，每次送完返回邮局。总耗时 = Σ(1→i 最短路径 + i→1 最短路径)。用 Dijkstra 在正向图上求 1 到所有点的最短路，再在反向图（边方向相反）上求 1 到所有点的最短路，后者即为各点到 1 的最短路。最后求和。

python

import heapq

def solve():
    data = list(map(int, sys.stdin.read().split()))
    it = iter(data)
    n = next(it); m = next(it)
    g = [[] for _ in range(n + 1)]
    rg = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = next(it); v = next(it); w = next(it)
        g[u].append((v, w))
        rg[v].append((u, w))

    def dijkstra(graph, start):
        dist = [float('inf')] * (n + 1)
        dist[start] = 0
        pq = [(0, start)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                nd = d + w
                if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        return dist

    d1 = dijkstra(g, 1)
    d2 = dijkstra(rg, 1)
    ans = sum(d1[i] + d2[i] for i in range(2, n + 1))
    print(ans)

if __name__ == "__main__":
    import sys
    solve()

M30910: 邮递员送快递 ​

M30910: 邮递员送快递