新年好——Dijkstra+Permutation

题目

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 5e4+10, M = 2e5+10;
const int inf = 0x3f3f3f3f; 
int n, m;
int a[6];
int h[N], e[M], ne[M], idx, w[M];
int dist[6][N];
int st[N];
unordered_map<int, int> mp;
void add(int a, int b, int c)  // 添加一条边a->b
{w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra(int s, int d[])
{memset(st, 0, sizeof st);priority_queue<PII, vector<PII>, greater<PII>> q;q.push({0, s}); d[s] = 0; st[s] = true;while(q.size()){int u = q.top().y; q.pop();st[u] = false;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];if(!st[j]) q.push({d[j], j}), st[j] = true;}}}
}
void out()
{for(int i = 0; i <= 5; i++)cout << a[i] << ' ';cout << '\n';
}
int main()
{cin >> n >> m;a[0] = 1, mp[1] = 0;for(int i = 1; i <= 5; i++){cin >> a[i];mp[a[i]] = 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);}memset(dist, 0x3f, sizeof dist);for(int i = 0; i <= 5; i++)dijkstra(a[i], dist[i]);sort(a+1, a+6);int ans = inf;do{int sum = 0;for(int i = 0; i+1 <= 5; i++){int t = dist[mp[a[i]]][a[i+1]];if(t == inf){sum = inf;break;}sum += t;}ans = min(ans, sum);}while(next_permutation(a+1, a+6));cout << ans;
}