新年好(dijkstra+dfs)

代码有点小长, 但是思路还是比较简单

• 第一步就是找到六个点(包括自己的编号)与其它各个点的最短路
• 第二步就是以编号1为原点, 然后暴搜其它五个点
• 就没了

C++代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 * 2 + 10, M = 5e4 + 10;

int h[N], w[N], e[N], ne[N], idx, n, m, a[10], df[10][10], d[M];
bool s[M], ds[10];

void add(int x, int y, int z)
{
    e[idx] = y; w[idx] = z;
    ne[idx] = h[x]; h[x] = idx++;
}

int res = 0x3f3f3f3f;
void dfs(int u, int cnt, int sub)
{
    if(cnt == 5)
    {
        res = min(res, sub);
        return ;
    }
    for(int i = 1; i < 6; i++)
    {
        if(!ds[i])
        {
            ds[i] = true;
            dfs(i, cnt + 1, sub + df[u][i]);
            ds[i] = false;
        }
    }
}

void dijkstra(int t)
{
    memset(d, 0x3f, sizeof(d));
    memset(s, 0, sizeof(s));
    d[t] = 0;
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0, t});

    while(q.size())
    {
        int ver = q.top().second;
        int dis = q.top().first;
        q.pop();

        if(s[ver]) continue;
        s[ver] = true;

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

}

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

    memset(h, -1, sizeof(h));

    for(int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }

    for(int i = 0; i < 6; i++)
    {
        dijkstra(a[i]);
        for(int j = 0; j < 6; j++)
        {
            df[i][j] = d[a[j]];
            df[j][i] = d[a[j]];
        }
    }

    dfs(0, 0, 0);

    cout << res << endl;

    return 0;
}