c/c++语言开发共享loj#10078. 新年好(最短路)

题目：

解析：

亲戚只有五个，可以把它们看成2,3,4,5,6号点，分别跑最短路，记录一下距离，然后dfs一下
这题非常玄学，我开了一个(12*12)的数组，没有离散化，竟然过了，开到(5050*5050)就re，玄学

代码：

#include <bits/stdc++.h> using namespace std;  const int n = 1e6 + 10; const int inf = 0x3f3f3f3f;  int n, m, num, cnt, ans = inf; int head[n], dis[n], home[n], d[12][12];  bool vis[n], mark[n];  struct node {     int v, nx, w; } e[n];  struct edge {     int id, dis;     bool operator <(const edge &oth) const {         return this -> dis > oth.dis;     } };  inline void add(int u, int v, int w) {     e[++num] = (node) {v, head[u], w}, head[u] = num; }  priority_queue<edge>q; void dijkstra(int s) {     memset(dis, inf, sizeof dis);     memset(vis, 0, sizeof vis);     dis[s] = 0;     q.push((edge) {s, 0});     while (!q.empty()) {         edge d = q.top();         q.pop();         int u = d.id;         if (vis[u]) continue;         vis[u] = 1;         for (int i = head[u]; ~i; i = e[i].nx) {             int v = e[i].v;             if (dis[v] > dis[u] + e[i].w)                 q.push((edge) {v, dis[v] = dis[u] + e[i].w});         }     } }  void dfs(int u, int sum, int cnt) {     if (cnt == 5) {         ans = min(ans, sum);         return;     }     if (sum > ans) return;     for (int i = 2; i <= 6; ++i) {         if (!mark[i]) {             mark[i] = 1;             dfs(i, sum + d[u][i], cnt + 1);             mark[i] = 0;         }     } }  int main() {     memset(head, -1, sizeof head);     cin >> n >> m;     for (int i = 1; i <= 5; ++i) cin >> home[i];     for (int i = 1, x, y, z; i <= m; ++i)          cin >> x >> y >> z, add(x, y, z), add(y, x, z);     dijkstra(1);     for (int i = 1; i <= 5; ++i)         d[1][i + 1] = d[i + 1][1] = dis[home[i]];     for (int i = 1; i <= 5; ++i) {         dijkstra(home[i]);         for (int j = i + 1; j <= 5; ++j)              d[i + 1][j + 1] = d[j + 1][i + 1] = dis[home[j]];     }          mark[1] = 1;     dfs(1, 0, 0);     cout << ans << endl; }