洛谷 P5764 [CQOI2005]新年好

P5764 [CQOI2005]新年好

题目描述

重庆城里有 $n$ 个车站，$m$ 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 $1$，他有五个亲戚，分别住在车站 $a,b,c,d,e$。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

输入格式

第一行：$n,m$，分别为车站数目和公路的数目。

第二行：$a,b,c,d,e$，分别为五个亲戚所在车站编号。

以下 $m$ 行，每行三个整数 $x,y,t$，为公路连接的两个车站编号和时间。

输出格式

仅一行，包含一个整数 $T$，为最少的总时间。保证 $T\le 10^9$。

样例 #1

样例输入 #1

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

样例输出 #1

21

提示

对于 $40\%$ 的数据，有 $1\le n\le 500$，$1\le m\le 2000$。

对于 $100\%$ 的数据，有 $1\le n\le 50000$，$1\le m\le 100000$，$1\le a,b,c,d,e\le n$，$1\le x,y\le n$，$1\le t\le 10000$。

思路

起点确定，所到达的点集有限，且大小固定为5，非常小，于是我们可以爆搜访问点集中每个点的顺序，也就是全排列。在爆搜过程中我们需要知道当前点$x$到要访问的点$y$的最短距离，最短距离可以用很多算法求解，本题数据量可知所给出的图为稀疏图，范围比较大，首选堆优化的Dijkstra算法，最短距离需要预先处理，这样在爆搜的过程中离线查询即可。本题的存图方式比较常规，但是记录最短路有些讲究，我们需要开一个二维数组$dist[7][N]$，$dist[i][j]$表示$start[i]$到$j$的最短路，这样记录最短路的话，我们可以枚举会访问六个点到其他点的最短路。

参考代码（C++）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 50010, M = 200010, INF = 0x3f3f3f3f;int n, m, res;
int start[7], dist[7][N];
int h[N], e[M], ne[M], w[M], idx;
bool st[N], vis[6];void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}void dijkstra(int sr, int dist[]) {memset(st, 0, sizeof st);priority_queue<PII, vector<PII>, greater<PII>> que;dist[sr] = 0;que.push({0, sr});while(que.size()) {auto tt = que.top(); que.pop();if(st[tt.y]) continue;st[tt.y] = true;for(int i = h[tt.y]; ~i; i = ne[i]) {int j = e[i];if(dist[j] > tt.x + w[i]) {dist[j] = tt.x + w[i];que.push({dist[j], j});}}}
}void dfs(int u, int cost, int p) {if(u == 6) {res = min(res, cost);}if(cost > res) return ;for(int i = 2; i <= 6; i ++) {if(!vis[i]) {vis[i] = true;dfs(u + 1, cost + dist[p][start[i]], i);vis[i] = false;}}
}int main() {scanf("%d%d", &n, &m);start[1] = 1;for(int i = 2; i <= 6; i ++) scanf("%d", &start[i]);memset(h, -1, sizeof h);while(m --) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}memset(dist, 0x3f, sizeof dist);for(int i = 1; i <= 6; i ++) dijkstra(start[i], dist[i]);res = INF;dfs(1, 0, 1);printf("%d\n", res);return 0;
}

疑问

有疑问欢迎私信或者评论，看到消息会解答