二维数组存不同起点到其他点的最短距离,dfs求最短的一天路径,注意还原现场(最优解)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 50010;
const int M = 2e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
int source[N];
int dist[6][N];
bool st[N];
int n, m;
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(dist, 0x3f, 4 * N);//四个字节
memset(st, false, sizeof st);
priority_queue<PII, vector<PII>, greater<PII>>heap;
heap.push({ 0,start });
dist[start] = 0;
while (heap.size())
{
auto t = heap.top();
heap.pop();
if (st[t.y])continue;
st[t.y] = false;
for (int i = h[t.y]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t.y] + w[i])
{
dist[j] = dist[t.y] + w[i];
heap.push({ dist[j],j });
}
}
}
}
int dfs(int u, int start, int distance)
{
if (u == 6)return distance;
int res = 0x3f3f3f3f;
st[start]=true;
for (int i = 1; i <= 5; i++)
{
if (!st[i])
{
int next = source[i];
res = min(res, dfs(u + 1, i, dist[start][next] + distance));
}
}
st[start]=false;
return res;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
source[0] = 1;
for (int i = 1; i <= 5; i++)cin >> source[i];
while (m--)
{
int x, y, t;
cin >> x >> y >> t;
add(x, y, t), add(y, x, t);
}
for (int i = 0; i < 6; i++)dijkstra(source[i], dist[i]);
memset(st, false, sizeof st);
cout << dfs(1, 0, 0) << endl;
return 0;
}