题目链接
思路
亲戚很少，可以每个点都算一遍单源最短路
然后dfs错误原因
算错复杂度
#include#include #include #include using namespace std;const int inf = 0x3f3f3f3f;const int maxm = 2e5 + 7;const int maxn = 5e4 + 7;struct edge { int v, q, nxt;} e[maxm];struct node { int x, y; node(int a, int b) { x = a, y = b; } bool operator < (const node &b) const { return y > b.y; }};int head[maxm], tot;void add_edge(int u, int v, int q) { e[++tot].v = v; e[tot].q = q; e[tot].nxt = head[u]; head[u] = tot;}int n, m;int qinqi[7];int a[10][10];int dis[6][maxn];int read() { int x = 0, f = 1; char s = getchar(); for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1; for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0'; return x * f;}void dijstra(int s) { priority_queue q; q.push(node(qinqi[s], 0)); dis[s][qinqi[s]] = 0; while (!q.empty()) { node u = q.top(); q.pop(); if (dis[s][u.x] != u.y) continue; for (int i = head[u.x]; i; i = e[i].nxt) { int v = e[i].v; if (dis[s][v] > dis[s][u.x] + e[i].q) { dis[s][v] = dis[s][u.x] + e[i].q; q.push(node(v, dis[s][v])); } } }}int ans=inf;int vis[10];void dfs(int last,int js,int tot){ if(js==5) { ans=min(ans,tot); return; } if(tot > ans) { return; } for(int i=1;i<=5;++i) { if(!vis[i]) { vis[i]=1; dfs(i,js+1,tot+a[last][i]); vis[i]=0; } }}int main() { freopen("a.in", "r", stdin); memset(dis, inf, sizeof(dis)); n = read(), m = read(); qinqi[0] = 1; for (int i = 1; i <= 5; ++i) qinqi[i] = read(); for (int i = 1; i <= m; ++i) { int x = read(), y = read(), z = read(); add_edge(x, y, z); add_edge(y, x, z); } for (int i = 0; i <= 5; ++i) { dijstra(i); } for (int i = 0; i <= 5; ++i) { for (int j = 0; j <= 5; ++j) { a[i][j] = dis[i][qinqi[j]]; } } dfs(0,0,0); cout<