题目描述

blablabla

样例

blablabla

算法1

这道题，我们有多个起点，那么我们不妨就反着建边，从终点向多个起点跑spfa，最后再取min就行

C++ 代码

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

    vis[u]=1;
    d[u]=0;
    q.push(u);
    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;
                }
            }
        }
    }
}
int main()
{        int n,m,s;
    while(scanf("%d%d%d",&n,&m,&s)!=-1){
    memset(d,0x3f,sizeof(d));
    memset(head,-1,sizeof(head));

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(y,x,z);
    }
    int p;
    cin>>p;
    int x;
    int ans=inf;
    spfa(s);
    // for(int i=1;i<=n;i++)
    // cout<<d[i]<<endl;
    for(int i=1;i<=p;i++)
    {
        cin>>x;
        ans=min(ans,d[x]);
    }
    if(ans==inf)
    cout<<-1<<endl;
    else 
    cout<<ans<<endl;
    }
}