解决方案

最短路 + 枚举

分析

有规定好的五个亲戚即五个节点必须经过，要求你找到一种经过五个亲戚的方法保证最后所需要的时间最少。

我们发现亲戚节点只有五个我们可以枚举以下这五个点访问顺序先后的所有情况，然后直接找到其中代价最小的一种情况即可

其实关键点还是在于我们想要知道每个点道每个点之间的最短距离需要用单源最短路，也可以用全局最短路，但是此处不适用，但是必要要在点的数量足够小的情况下。

这样我们对每个点跑一次单元最短路再去枚举所有的方案，然后从中找到一种最小的方案即可

此类型适用于所有的方案数都可以枚举得到，并且给定的方案数不多的情况，这种情况我们可以预先处理出来所要求的点与点之间的最短距离并保存下来

时间复杂度

$O(mlog_n)$

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int M = 200010;

struct edge {   
    int w, to, next;
}e[M];

int head[N], tot;
int n, m;
void add(int a,int b,int c)
{
    e[++tot].to = b;
    e[tot].next = head[a];
    e[tot].w = c;
    head[a] = tot;
}

vector<int> dijkstra(int s)
{
    int dis[N];
    bool vis[N];
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    priority_queue<pair<int,int>> q;

    dis[s] = 0;
    q.push({0, s});

    while(!q.empty())
    {
        int x = q.top().second;q.pop();

        if(vis[x]) continue;

        vis[x] = 1;

        for(int i = head[x]; i != -1; i = e[i].next)
        {
            int y = e[i].to, w = e[i].w;
            if(dis[y] > dis[x] + w)
            {
                dis[y] = dis[x] + w;
                q.push({-dis[y], y});
            }
        }
    }
    vector<int> res(dis, dis + N);
    return res;
}

int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m;
    vector<int> s(5);
    for(int i = 0; i < 5; i ++)cin >> s[i];

    int k = m;
    while(k --)
    {
        int x, y, t;
        cin >> x >> y >> t;
        if(x == y)continue;
        add(x, y, t);
        add(y, x, t);
    }

    unordered_map<int,vector<int>> f;
    f[1] = dijkstra(1);
    for(int x : s)
    {
        f[x] = dijkstra(x);
    }

    int ans = 0x3f3f3f3f;
    sort(s.begin(),s.end());
    do{
        int cost = f[1][s[0]];
        for(int i = 0; i < s.size() - 1; i ++)
        {
            int x = s[i], y = s[i + 1];
            cost += f[x][y];
        }
        ans = min(ans, cost);
    }while(next_permutation(s.begin(),s.end()));
    cout << ans << endl;

    return 0;
}