预处理再搜索,不然大约是2 * 10^8,会T两个点
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10, M = 2 * N, inf = 0x3f3f3f3f;
int n, m;
int id[10];
int h[N], e[M], w[M], ne[M], idx;
int dist[10][N];
bool st[N], flag[10];
int ans = inf;
void add(int a, int b, int v)
{
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int last, int sum, int cnt)
{
if(cnt > ans) return;
if(sum == 5)
{
ans = min(ans, cnt);
return;
}
for(int i = 1; i <= 5; i ++)
{
if(!flag[i])
{
flag[i] = 1;
dfs(i, sum + 1, cnt + dist[last][id[i]]);
flag[i] = 0;
}
}
}
void dijkstra(int index, int start)
{
for(int i = 0; i <= n; i ++) dist[index][i] = inf;
dist[index][start] = 0;
memset(st, 0, sizeof st);
priority_queue<pii, vector<pii>, greater<pii>> heap;
heap.push({0, start});
while(heap.size())
{
pii t = heap.top();
heap.pop();
int d = t.x, u = t.y;
if(st[u]) continue;
st[u] = 1;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(dist[index][j] > dist[index][u] + w[i])
{
dist[index][j] = dist[index][u] + w[i];
heap.push({dist[index][j], j});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= 5; i ++) cin >> id[i];
for(int i = 0; i < m; i ++)
{
int x, y, t;
cin >> x >> y >> t;
add(x, y, t), add(y, x, t);
}
id[0] = 1;
for(int i = 0; i <= 5; i ++) dijkstra(i, id[i]);
dfs(0, 0, 0);
cout << ans << endl;
return 0;
}
请问代码的评论是怎么发的?