1135. 新年好 题解

#include <bits/stdc++.h>
using namespace std;
const int N = 50010, M = 100010 << 1;
typedef pair<int, int> PII;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[6][N], source[N];  // 因为是6个人，所以dist第一维开成6
bool vis[N];

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, N * 4); // int 4个字节，所以大小是4*N
    dist[start] = 0;
    memset(vis, false, sizeof vis);
    
    priority_queue<PII, vector<PII>, greater<PII> >q;
    q.push({0, start});

    while (q.size())
    {
        auto t = q.top();
        q.pop();

        int ver = t.second;
        if (vis[ver])    continue;
        vis[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                q.push({dist[j], j});
            }
        }
    }
}

// 枚举每种拜访次序，求出最小距离
// 拜访了u个人，自己是第1个人；当前起点是source[start]，当前走过的距离是distanc
int dfs(int u, int start, int distance)
{
    if (u == 6) return distance;   // u== 6表示：拜访完5个亲戚，此时返回最短路
    
    int res = 0x3f3f3f3f;  // res存距离最短的分支
    for (int i = 1; i <= 5; i++)
        if (!vis[i])
        {
            int next = source[i];  // 走亲戚i
            vis[i] = true;
            res = min(res, dfs(u + 1, i,distance + dist[start][next]));
            vis[i] = false;
        }
    return res;
}

int main()
{
    cin >> n >> m;
    source[0] = 1;
    for (int i = 1; i <= 5; i++)    cin >> source[i];

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    // 6 个点，分别求最短路
    for (int i = 0; i < 6; i++) dijkstra(source[i], dist[i]); 
    /*
    1. 共有6个人，起点是自己：第1个人
    2. 当前是source[0]：佳佳
    3. 当前走过的距离是0
    */
    memset(vis, false, sizeof vis);  // 这里初始化是为了下面的dfs,清除上面dijkstra的遗留
    cout << dfs(1, 0, 0);
    return 0;
}