F - Dragon Ball I ——最短路

X星球上有一个关于龙珠的传说：如果有人收集到七个龙珠，龙神就会出现并帮助你实现愿望。
有一天，你惊讶地发现这个故事可能是真的：你在跳蚤市场发现了一个龙珠雷达！雷达会向你显示X星球上七个龙珠的位置。你想不失时机地检查关于为自己许愿的古老传说的真相！
行星X上总共有 n 个城市，编号从 1 到 n 。你目前在城市 1 。要从一个城市到另一个城市，你可以乘坐任意数量的 m 条双向传送之旅。第 i 条传送门每次使用的成本为 ti 枚硬币，它可以将你传送到城市 ai 和 bi 之间。要收集一颗龙珠，你只需要访问雷达上标示的龙珠所在的城市。同一个城市可能有多颗龙珠；在这种情况下，如果你访问了该城市，你可以一次性捡起所有的龙珠。

输入
第一行输入包含两个空格分隔的整数 n和 m（ 1≤n，m ≤2 00000），城市数量和可能的传送行程。然后跟随 包含三个空格分隔整数的 m 行 ai​,bi​,和 ti​ （1 ≤ ai​,bi​ ≤ n,0≤ ti​ ≤ 10000），如上所述，其表示通过传送旅程连接的两个城市，以及使用传送机的成本。然后跟随一行七个空格分隔的整数，代表雷达上显示的七个龙珠的城市ID。每个ID c 满足界 1 ≤ c ≤ n。

输出
打印收集龙珠雷达上显示的所有七个龙珠所需的最低硬币数量。如果无法完成此任务，请打印 −1。

Input1
10 9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 2 3 4 5 6 7

Output1
6

Input2
5 5
1 2 0
1 3 0
2 3 1
3 4 1
4 5 1
1 2 1 2 3 4 4

Output2
1

解析：
问题就是按照什么顺序来取龙珠，才能花最少的硬币。
从起点开始出发，就算 7 个龙珠都在不同的地方，全排列也不超时，所以枚举排列顺序，计算每次所花的硬币数，取最小。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e5+10;
int n,m;
struct node
{
    int v,w;
};
vector <node> g[N];
int d[8][N];                                    //一共8条最短路
bool vis[N];
priority_queue <PII,vector<PII>,greater<PII>> q;
void djkstra(int cnt,int x)
{
    memset(vis,0,sizeof vis);
    d[cnt][x]=0;
    q.push({0,x});
    while (q.size())
    {
        int tance=q.top().first;
        int u=q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u]=1;
        for (auto [v,w]:g[u])
        {
            if (d[cnt][v]>tance+w)
            {
                d[cnt][v]=tance+w;
                q.push({d[cnt][v],v});
            }
        }
    }
}
int ans;
int a[10],k[10];
void dfs(int u)
{
    if (u>=7)
    {
        int l=0,r=0,sum=0;
        for (int i=0;i<7;i++)
        {
            r=a[i];
            sum +=d[l][k[a[i]]];
            l=a[i];
        }
        ans=min(ans,sum);
        return ;
    }
    for (int i=1;i<=7;i++)
    {
        if (!vis[i])
        {
            a[u]=i;
            vis[i]=1;
            dfs(u+1);
            vis[i]=0;
        }
    }
}
void solve()
{
    cin>>n>>m;
    for (int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    memset(d,0x3f,sizeof d);
    djkstra(0,1);
    for (int i=1;i<=7;i++)
    {
        int x;
        cin>>x;
        k[i]=x;                                 //离散化一下，不用去重
        djkstra(i,x);
    }
    memset(vis,0,sizeof vis);
    ans=1e18;
    dfs(0);                                     //全排列，枚举每一种取法
    if (ans==1e18) cout<<-1;
    else cout<<ans;
}
signed main()
{
    ios;
    int T=1;
    //cin>>T;
    while (T--) solve(); 
    return 0;
}