题：https://nanti.jisuanke.com/t/41349

分析：对于hero来说，走单源最短路，然后遍历dis数组中的最大值即可找到，对于消防员来说，走多源最短路，只需要建个超级起点连接各个消防点，边权为0走spfa即可出dis数组

注意：得无向边

#include
      
       using namespace std;typedef long long ll;const ll INF=1e18;const int M=2e3+3;ll dist[M];struct node{    int v,nextt;    ll w;}e[(M*M)<<1];int tot,vis[M],head[M],a[M],sign[M];void addedge(int u,int v,ll w){    e[tot].v=v;    e[tot].nextt=head[u];    e[tot].w=w;    head[u]=tot++;}void spfa(int s){    queue
       
        q;    while(!q.empty())        q.pop();    memset(dist,0x7f,sizeof dist);    //cout<
        
         <
         
          dist[u]+e[i].w) {                dist[v]=dist[u]+e[i].w;                if(!vis[v]) {                    vis[v]=true;                    q.push(v);                }            }        }    }}int main(){    int t;    scanf("%d",&t);    while(t--){        int n,m,he,k,C,s=0;        scanf("%d%d%d%d%d",&n,&m,&he,&k,&C);        for(int i=0;i<=n;i++)            head[i]=-1,sign[i]=0;        tot=0;        for(int i=1;i<=k;i++)            scanf("%d",&a[i]),sign[a[i]]=1;        while(m--) {            int u,v;            ll w;            scanf("%d%d%lld",&u,&v,&w);            addedge(u,v,w);            addedge(v,u,w);        }        spfa(he);        ll maxxhe=0ll;        for(int i=1;i<=n;i++)            maxxhe=max(maxxhe,dist[i]);        for(int i=1;i<=k;i++)            addedge(s,a[i],0);        spfa(s);        ll maxxren=0ll;        for(int i=1;i<=n;i++){            if(sign[i]==0)                maxxren=max(dist[i],maxxren);        }        maxxren*=1ll*C;    //    cout<
          
           <<"!!"<
           
            <