题目描述
重庆城里有 $n$ 个车站,$m$ 条 双向 公路连接其中的某些车站。
每两个车站最多用一条公路连接,从任何一个车站出发都可以经过一条或者多条公路到达其他车站,但不同的路径需要花费的时间可能不同。
在一条路径上花费的时间等于路径上所有公路需要的时间之和。
佳佳的家在车站 $1$,他有五个亲戚,分别住在车站 $a,b,c,d,e$。
过年了,他需要从自己的家出发,拜访每个亲戚(顺序任意),给他们送去节日的祝福。
怎样走,才需要最少的时间?
输入格式
第一行:包含两个整数 $n,m$,分别表示车站数目和公路数目。
第二行:包含五个整数 $a,b,c,d,e$,分别表示五个亲戚所在车站编号。
以下 $m$ 行,每行三个整数 $x,y,t$,表示公路连接的两个车站编号和时间。
输出格式
输出仅一行,包含一个整数 $T$,表示最少的总时间。
数据范围
$1 \le n \le 50000$,
$1 \le m \le 10^5$,
$1 < a,b,c,d,e \le n$,
$1 \le x,y \le n$,
$1 \le t \le 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
C++ 代码
// 6 遍堆优化版Dijkstra, 最短距离存起来
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 50010, M = 200010;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int dist[6][N];
int r[6];
int n, m, ans;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void Dijkstra(int start, int dist[])
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, N * 4); // 初始化指定大小的dist, 也即每一次的 dist
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
heap.push({dist[start], start});
while(heap.size())
{
int distance = heap.top().first;
int u = heap.top().second;
heap.pop();
if(st[u]) continue;
st[u] = true;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
return ;
}
// 当前在 r[u] 站点, 已经走了 cnt 家亲戚, 共花费时间为 cost
void dfs(int u, int cnt, int cost)
{
if(cost >= ans) return ; // 最优性剪枝
if(cnt == 5) ans = cost;
if(u > 5 || cnt > 5) return ; // 可行性剪枝
for(int i = 1; i < 6;i ++)
{
if(st[r[i]] == false && u != i)
{
st[r[i]] = true;
dfs(i, cnt + 1, cost + dist[u][r[i]]);
st[r[i]] = false;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
r[0] = 1;
for(int i = 1;i < 6;i ++) cin >> r[i];
int x, y, t;
memset(h, -1, sizeof h);
while(m --)
{
cin >> x >> y >> t;
add(x, y, t), add(y, x, t);
}
for(int i = 0;i < 6;i ++) Dijkstra(r[i], dist[i]);
memset(st, 0, sizeof st);
ans = 1 << 30;
dfs(0, 0, 0);
cout << ans << endl;
return 0;
}