Loading... # ACWing 1135 新年好 题解 ## 题目描述 重庆城里有$n$个车站, $m$条**双向**公路连接其中的某些车站。 每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。 在一条路径上花费的时间等于路径上所有公路需要的时间之和。 佳佳的家在车站$1$，他有五个亲戚，分别住在车站$a, b, c, d, e$ 过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。 怎样走，才需要最少的时间？ ## 输入 第一行：包含两个整数$n, m$分别表示车站数目和公路数目。 第二行：包含五个整数 $a, b, c, d, e$，分别表示五个亲戚所在车站编号。 以下$m$行，每行三个整数$x, y, t$，表示公路连接的两个车站编号和时间。 ## 输出 输出仅一行，包含一个整数$T$，表示最少的总时间。 ## 解题思路 对于本题来说， 最朴素的解题思路为：枚举所有不同的排列$p_1, p_2, p_3, p_4, p_5$， 分别计算每一个排列当中从$p_i$到$p_{i + 1}$的最短距离。假设使用spfa来求最短路， 时间复杂度为$O(5!\times 10^5 \times 4) = O(10^8)$， 因此一定会超时 所以这道题可以考虑如下优化： - 首先先预处理出来从$p_i$出发到所有节点的最小值数组`dist[i]`， 这样在随后的搜索过程中只需要去查表 - 然后采用DFS动态更新过程的最小值 通过以上优化方式， 时间复杂度为$O(5\times 10^5 + 5!)$, 因此可以过掉所有的测试用例 ## AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <queue> #define endl '\n' using namespace std; const int N = 2e5 + 10; typedef pair<int, int> PII; int n, m; int h[N], e[N], ne[N], w[N], idx; int dist[6][N]; int st[N]; int a[N]; int ans = 0x3f3f3f3f; void add(int a, int b, int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++; } void dijstra(int x, int d[]) { memset(d, 0x3f, sizeof d[0] * N); memset(st, 0, sizeof st); priority_queue<PII, vector<PII>, greater<PII>> heap; d[x] = 0; heap.push({0, x}); while(heap.size()) { auto t = heap.top(); heap.pop(); int dis = t.first, u = t.second; if(st[u]) continue; st[u] = true; for(int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(d[j] > d[u] + w[i]) { d[j] = d[u] + w[i]; heap.push({d[j], j}); } } } } void dfs(int u, int sum, int cnt) { if(cnt == 5) { ans = min(ans, sum); return ; } for(int i = 1; i <= 5; i ++) { if(st[i]) continue; st[i] = true; dfs(i, sum + dist[u][a[i]], cnt + 1); st[i] = false; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; a[0] = 1; for(int i = 1; i <= 5; i ++) cin >> a[i]; memset(h, -1, sizeof h); for(int i = 1; i <= m; i ++) { int x, y, t; cin >> x >> y >> t; add(x, y, t); add(y, x, t); } for(int i = 0; i <= 5; i ++) dijstra(a[i], dist[i]); memset(st, 0, sizeof st); dfs(0, 0, 0); cout << ans << endl; return 0; } ``` 最后修改：2025 年 03 月 10 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏