1129 热浪（单源最短路径模板）

港控/mmm° 2022-09-15 15:50 143阅读 0赞

**1. 问题描述：**

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。  
这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。除了起点和终点外的每个城镇都由双向道路连向至少两个其它的城镇。每条道路有一个通过费用（包括油费，过路费等等）。给定一个地图，包含 C 条直接连接 2 个城镇的道路。每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。

**输入格式**

第一行: 4 个由空格隔开的整数: T，C，Ts，Te；第 2 到第 C+1 行：第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs，Re，Ci。

**输出格式**

一个单独的整数表示从 Ts 到 Te 的最小总费用。数据保证至少存在一条道路。

**数据范围**

1 ≤ T ≤ 2500，  
1 ≤ C ≤ 6200，  
1 ≤ Ts，Te，Rs，Re ≤ T，  
1 ≤ Ci ≤ 1000

**输入样例：**

7 11 5 4  
2 4 2  
1 4 3  
7 2 2  
3 4 3  
5 7 5  
7 3 3  
6 1 1  
6 3 4  
2 4 3  
5 6 3  
7 2 1

**输出样例：**

7  
来源：[https://www.acwing.com/problem/content/description/1131/][https_www.acwing.com_problem_content_description_1131]

**2. 思路分析：**

分析题目可以知道这是一道单源最短路径的裸题，题目中的所有边都是正的，而且数据规模不是特别大，所以我们选择自己最熟悉最短路径算法解决即可。

**3. 代码如下：**

**朴素版本的dijkstra算法：**

from typing import List
    
    
    class Solution:
        # 朴素版本的dijkstra算法
        def dijkstra(self, s: int, t: int, n: int, g: List[dict]):
            vis = [0] * (n + 1)
            INF = 10 ** 9
            dis = [INF] * (n + 1)
            dis[s] = 0
            for i in range(n):
                k = -1
                for j in range(1, n + 1):
                    if vis[j] == 0 and (k == -1 or dis[k] > dis[j]):
                        k = j
                vis[k] = 1
                # 枚举以当前的点为中间点看距离是否更短
                for next in g[k].items():
                    if vis[next[0]] == 0 and dis[next[0]] > dis[k] + next[1]:
                        dis[next[0]] = dis[k] + next[1]
            return dis[t]
    
        def process(self):
            n, m, s, t = map(int, input().split())
            # 每一个g[i]都是一个字典
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                # 因为是无向图所以需要建两次, 下面是判断重边的情况
                if y in g[x]:
                    g[x][y] = min(g[x][y], z)
                else:
                    g[x][y] = z
                if x in g[y]:
                    g[y][x] = min(g[y][x], z)
                else:
                    g[y][x] = z
            return self.dijkstra(s, t, n, g)
    
    
    if __name__ == "__main__":
        print(Solution().process())

**堆优化版本的dijkstra算法：**

from typing import List
    import heapq
    
    
    class Solution:
        # 堆优化版本的dijkstra算法
        def dijkstra(self, s: int, t: int, n: int, g: List[dict]):
            vis = [0] * (n + 1)
            INF = 10 ** 9
            dis = [INF] * (n + 1)
            dis[s] = 0
            q = list()
            heapq.heappush(q, (0, s))
            while q:
                cur = heapq.heappop(q)
                if vis[cur[1]] == 1: continue
                vis[cur[1]] = 1
                for next in g[cur[1]].items():
                    if dis[next[0]] > cur[0] + next[1]:
                        dis[next[0]] = cur[0] + next[1]
                        heapq.heappush(q, (dis[next[0]], next[0]))
            return dis[t]
    
        def process(self):
            n, m, s, t = map(int, input().split())
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                if y in g[x]:
                    g[x][y] = min(g[x][y], z)
                else:
                    g[x][y] = z
                if x in g[y]:
                    g[y][x] = min(g[y][x], z)
                else:
                    g[y][x] = z
            return self.dijkstra(s, t, n, g)
    
    
    if __name__ == "__main__":
        print(Solution().process())

**spfa算法：**

from typing import List
    import collections
    
    
    class Solution:
        def spfa(self, s: int, t: int, n: int, g: List[dict]):
            # 双端队列
            q = collections.deque()
            # 队列中只存一个节点的编号即可, 因为某个点的到起点的最短距离存储在了dis中
            q.append(s)
            # 标记某个点是否被修改, 好像声明为布尔值比整型列表会快一点
            vis = [False] * (n + 1)
            vis[s] = True
            INF = 10 ** 9
            dis = [INF] * (n + 1)
            # 自己到自己的距离为0
            dis[s] = 0
            while q:
                p = q.popleft()
                vis[p] = False
                for next in g[p].items():
                    # 通过当前的节点p到下一个点的距离更短了说明需要将修改的点存储到队列中
                    if dis[next[0]] > dis[p] + next[1]:
                        dis[next[0]] = dis[p] + next[1]
                        # 判断发生修改的节点是否在队列中
                        if vis[next[0]] == 0:
                            q.append(next[0])
                            vis[next[0]] = True
            return dis[t]
    
        def process(self):
            n, m, s, t = map(int, input().split())
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                if y in g[x]:
                    g[x][y] = min(g[x][y], z)
                else:
                    g[x][y] = z
                if x in g[y]:
                    g[y][x] = min(g[y][x], z)
                else:
                    g[y][x] = z
            return self.spfa(s, t, n, g)
    
    
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_description_1131]: https://www.acwing.com/problem/content/description/1131/