P5764 [CQOI2005]新年好

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例 #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%40\%40% 的数据，有 1≤n≤5001≤n≤5001≤n≤500，1≤m≤20001≤m≤20001≤m≤2000。

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

思路

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

参考代码（C++）

#include 
#include 
#include 
#include #define x first
#define y secondusing namespace std;typedef pair 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, greater> 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;
}

疑问

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