1135 新年好（单源最短路径 + dfs）

淡淡的烟草味﹌ 2022-08-28 05:55 104阅读 0赞

**1. 问题描述：**

重庆城里有 n 个车站，m 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。佳佳的家在车站 1，他有五个亲戚，分别住在车站 a，b，c，d，e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

**输入格式**

第一行：包含两个整数 n，m，分别表示车站数目和公路数目。第二行：包含五个整数 a，b，c，d，e，分别表示五个亲戚所在车站编号。以下 m 行，每行三个整数 x，y，t，表示公路连接的两个车站编号和时间。

**输出格式**

输出仅一行，包含一个整数 T，表示最少的总时间。

**数据范围**

1 ≤ n ≤ 50000，  
1 ≤ m ≤ 10 ^ 5，  
1 < a，b，c，d，e ≤ n，  
1 ≤ x，y ≤ n，  
1 ≤ t ≤ 100

**输入样例：**

6 6  
2 3 4 5 6  
1 2 8  
2 3 3  
3 4 4  
4 5 5  
5 6 2  
1 6 7

**输出样例：**

21  
来源：[https://www.acwing.com/problem/content/1137/][https_www.acwing.com_problem_content_1137]

**2. 思路分析：**

分析题目可以知道将题目抽象为n个点和m条边的无向图，我们需要从1号起点出发，分别拜访1号点的编号为a，b，c，d，e的亲戚，拜访亲戚的顺序是任意的，我们需要求解出从1号点出发拜访完全部亲戚花费的最小时间。因为a，b，c，d，e这五点每一个点至少访问一次，所以顺序是不固定的，所以我们需要枚举这五个点所有可能的拜访顺序，求解五个点的排列顺序中点与点之间的最短路径即可。最容易想到的是先暴力枚举五个点的所有排列顺序（5!个），然后使用最短路径算法求解对应排列顺序的每一个点到下一个点的最短距离即可，搜索的时候得到排列顺序是固定的，所以我们只需要对每一个排列求解一遍最短路径得到最短距离即可。但是对于每一个排列顺序都使用最短路径算法求解的时间复杂度有点高，是乘法级别的，如果为spfa那么时间复杂度为O（5! \* 5m），所以时间复杂度还是比较高的，对于朴素版本的dijkstra算法的时间复杂度为O(5! \* 5 \* n ^ 2)，n = 50000肯定会超时的，堆优化版的时间复杂度为O(5! \* 5 \* mlogn) 也会超时，所以我们必须降低时间复杂度才可以通过。因为在暴力枚举的时候求解得到的亲戚的每一个排列的顺序都是固定的，所以我们可以先调整一下求解的顺序，先预处理以a，b，c，d，e每一个点出发到其余点的最短距离，将结果存储到二维数组dis中，二维数组的第一维表示以某个亲戚为起点，第二维记录从当前亲戚到其余点的最短距离，然后再求解求解出a，b，c，d，e五个点的全排列，在递归求解全排列的时候根据每一个得到的排列查表得到每一个亲戚与亲戚之间的最短距离即可，这样就可以将时间复杂度降为加法的形式，若为spfa时间复杂度为O(5! + 6m)，对于这道题目来说会卡spfa所以可以使用堆优化版的dijkstra算法来求解。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    import heapq
    
    
    class Solution:
        # u表示递归到当前排列的第u个亲戚, start表示当前的起点, source表示所有亲戚, vis表示是否被访问
        # 这里在递归生成全排列的时候使用的是标记法来生成的, 判断当前位置是否被标记如果被标记了说明之前已经使用过这个位置的数字了
        def dfs(self, u: int, start: int, source: List[int], vis: List[int], dis: List[List[int]]):
            # 当u大于5之后说明所有亲戚都已经求解完了
            if u > 5: return 0
            res = 10 ** 10
            for i in range(1, 6):
                if vis[i] == 0:
                    t = source[i]
                    vis[i] = 1
                    a = self.dfs(u + 1, i, source, vis, dis)
                    res = min(res, dis[start][t] + a)
                    # 回溯
                    vis[i] = 0
            return res
    
        # 堆优化版的dijkstra算法, 这道题目由于数据范围有点大所以使用朴素版的dijkstra和spfa都会超时, 只能够使用堆优化版的dijkstra算法
        def dijkstra(self, s: int, n: int, g: List[dict], dis: List[int]):
            q = list()
            heapq.heappush(q, (0, s))
            vis = [0] * (n + 1)
            dis[s] = 0
            while q:
                p = heapq.heappop(q)
                if vis[p[1]] == 1: continue
                vis[p[1]] = 1
                for next in g[p[1]].items():
                    if dis[next[0]] > p[0] + next[1]:
                        dis[next[0]] = p[0] + next[1]
                        heapq.heappush(q, (dis[next[0]], next[0]))
    
        def process(self):
            n, m = map(int, input().split())
            # 各个亲戚的编号, 1为佳佳家的编号
            source = [1] + list(map(int, input().split()))
            # 每一个g[i]为一个字典相当于是邻接表
            g = [dict() for i in range(n + 1)]
            INF = 10 ** 10
            dis = [[INF] * (n + 1) for i in range(6)]
            for i in range(m):
                x, y, z = map(int, input().split())
                # 这道题目是没有重边的所以不用特判
                g[x][y] = g[y][x] = z
            # 先做一遍最短路径, 这里需要注意下标
            for i in range(6):
                # 求解以亲戚中的每一个点作为起点到其余点的最短距离, 将结果存储到二维列表dis中
                # 相当于是空间换时间
                self.dijkstra(source[i], n, g, dis[i])
            vis = [0] * (n + 1)
            return self.dfs(1, 0, source, vis, dis)
    
    
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_1137]: https://www.acwing.com/problem/content/1137/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/12dfe7e04a464a17b5a239f1b00d48b4.png