思路：从终点出发反向做一次最短路，然后在所有能选的起点中选min

既然朋友家的车站都叫s了，是不是在提示我们什么）
注意一下反向加边

算法

spfa和dijkstra都没问题，这里写的dijkstra

时间复杂度

T*mlogn

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int M=2e5+5,N=1005;
int h[M],nex[M],to[M],w[M],cnt=1,n,m,aff,p,q,t,s,e,dist[N],ans;
bool vis[N];
inline void add(int a,int b,int c){
    to[cnt]=b,w[cnt]=c,nex[cnt]=h[a],h[a]=cnt++;
}
inline void init(){
    memset(vis,0,sizeof vis);
    memset(h,0,sizeof h);
    cnt=1;
    memset(dist,0x3f,sizeof dist);
    ans=0x3f3f3f3f;
}

void dijkstra(){
    priority_queue <pii,vector<pii>,greater<pii>>q;
    q.push({0,s});
    while(!q.empty()){
        auto hh=q.top();
        int nn=hh.second,dd=hh.first;
        q.pop();
        //printf("%d %d\n",nn,dd);
        if(vis[nn])continue;
        vis[nn]=true;
        for(int i=h[nn];i;i=nex[i]){
            int ni=to[i];
            if(dist[ni]>dd+w[i]){
                dist[ni]=dd+w[i];
                q.push({dist[ni],ni});
            }
        }
    }
}
int main(){
    while(cin>>n>>m>>s){
        init();
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&p,&q,&t);
            add(q,p,t);
        }
        dist[s]=0;
        dijkstra();
        cin>>aff;
        while(aff--){
            scanf("%d",&e);
            ans=min(ans,dist[e]);
        }
        printf("%d\n",ans==0x3f3f3f3f?-1:ans);
    }
    return 0;
}