题目描述

blablabla

样例

blablabla

算法1

直接跑spfa，

C++ 代码

#include<bits/stdc++.h>
using namespace std;
queue<int >q;
const int maxn=1e6;
bool vis[maxn];
long long d[maxn];
long long num[maxn];
const int inf=0x3f3f3f3f;
int n,m,p;
int ne[maxn],ver[maxn],head[maxn],cnt,e[maxn];
void add(int u,int v,int c)
{
    ne[cnt]=head[u];
    ver[cnt]=v;
    e[cnt]=c;
    head[u]=cnt;
    cnt++;
}

long long spfa(int u)
{   
    memset(d,0x7f,sizeof(d));
    memset(vis,0,sizeof(vis));
    q.push(u);
    d[u]=0;
    vis[u]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=ne[i])
        {
            int y=ver[i];
            if(d[y]>d[x]+e[i])
            {
                d[y]=d[x]+e[i];
                if(vis[y]==0)
                {   
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
    long long res=0;
    // for(int i=1;i<=n;i++)
    // cout<<num[i]<<" "<<d[i]<<endl;
    for(int i=1;i<=n;i++)
        res=(res+num[i]*d[i]);
    return res;
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d%d",&p,&n,&m);
    for(int i=1;i<=p;i++)
    {
        int x;
        cin>>x;
        num[x]++;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    // for(int i=1;i<=n;i++)
    // spfa(i),puts(" ");
    long long ans=inf;
    for(int i=1;i<=n;i++)
    ans=min(ans,spfa(i));
    cout<<ans<<endl;
}