★实验任务

王尼玛又想出去旅游了，由于王尼玛是个抠门的人，所以王尼玛想要花最少的钱去一个自己想去的地方。王尼玛决定使用火车去旅行，地图上总共有n个城市，其中有k个城市是王尼玛想去玩的城市。由于王尼玛天天为公司加班加点，公司决定奖励他，免费送他去其中的m个城市（也就是说王尼玛能选择这m个城市中的一个作起点）。王尼玛数学不好，让你帮他选一条花费最少的路，这条路最终能到某一个他喜欢的城市。

★数据输入

第一行有四个整数n，T，m和k，表示有n个城市和T条路，公司奖励王尼玛其中m个城市，王尼玛喜欢其中的k个城市。

接下来有T行，每行有三个整数a，b，c，表示a城市和b城市火车通行的花费（火车通行是双向的）

接下来一行有m个整数，表示公司奖励的m个城市的编号。

最后一行有k个整数，表示王尼玛喜欢的k个城市的编号。

(2<=n<=50000,1<=T<=200000, 1<=m,k<=n ，数据保证王尼玛一定能到喜欢的城市)

★数据输出

每个样例输出一行，输出王尼玛能去某个喜欢的城市的最短花费。

输入示例

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

输出示例

9

★思路

dijkstra算法处理正边权图求单源最短路的本质是利用贪心的思想，每次利用离出发点最近的节点对图进行一次松弛操作每个点松弛一次，由于是正边权，这样后面的点就不会再改变前面的状态，即无后效性，而本题是在dijkstra算的基础上，可以从多个指定的起点出发，显然一个起点不可能去更新另一个起点（直接从另一个起点出发），可以看成所有起点之间的距离是0，所以，第一步松弛的时候，肯定是所有起点依次对图进行一次松弛（其他点不可能松弛起点），之后其他点再从小到大对图进行松弛，所以我们可以把所有起点合并成一个起点，再进行一次正常的dijkstra就能完成对问题的求解。

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define endl '\n'
#define INF 0x3f3f3f3f
const int M=1e9+7;
typedef long long ll; 
int n,T,m,k,flag1[200005],dis[2000005],head[200005],flag,a[200005][3],b[200005],via[200005];
struct node{
    int to,next,x;
}p[400005];
void add(int x,int y,int k){
    p[++flag].to=y;
    p[flag].x=k;
    p[flag].next=head[x];
    head[x]=flag;
}
struct node1{
    int x,y;
    friend bool operator <(node1 a,node1 b){
        return a.y>b.y;
    }
};
void disk(){
    priority_queue<node1> q;
    for(int i=1;i<=n;i++){
        dis[i]=1e9;
    }
    dis[n+1]=0;
    q.push({n+1,0});
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(flag1[x]) continue;
        flag1[x]=1;
        for(int i=head[x];i;i=p[i].next){
            if(dis[p[i].to]>dis[x]+p[i].x){
                dis[p[i].to]=dis[x]+p[i].x;
                q.push({p[i].to,dis[p[i].to]});
            }
        }
    }
}
int main(){
    cin>>n>>T>>m>>k;
    for(int i=1;i<=T;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    for(int i=1;i<=m;i++){
        int l;
        cin>>l;
        via[l]=1;
    }
    for(int i=1;i<=k;i++){
        cin>>b[i];
    }
    for(int i=1;i<=T;i++){
        if(via[a[i][0]]) a[i][0]=n+1;
        if(via[a[i][1]]) a[i][1]=n+1;
        if(a[i][0]==a[i][1]) continue;
        else {
            add(a[i][0],a[i][1],a[i][2]);
            add(a[i][1],a[i][0],a[i][2]);
        }
    }
    disk();
    int ans=1e9;
    for(int i=1;i<=k;i++){
        ans=min(dis[b[i]],ans);
    }
    cout<<ans;
}