Metropolis(多源点最短路)

Metropolis

https://www.nowcoder.com/acm/contest/203/I

题目描述

魔方国有n座城市，编号为。城市之间通过n-1条无向道路连接，形成一个树形结构。
在若干年之后，其中p座城市发展成了大都会，道路的数量也增加到了m条。
大都会之间经常有贸易往来，因此，对于每座大都会，请你求出它到离它最近的其它大都会的距离。

输入描述:

第一行三个整数n,m,p (1 ≤ n,m ≤ 2*10

,2 ≤ p ≤ n)，第二行p个整数

表示大都会的编号 (1≤ x

≤ n)。接下来m行每行三个整数a

,b

,l

表示一条连接a

和b

，长度为l

的道路 (1 ≤ a

,b

≤ n,1 ≤ l

≤ 10

)。
保证图是连通的。

输出描述:

输出一行p个整数，第i个整数表示x

的答案。

输入例子:

5 6 3

2 4 5

1 2 4

1 3 1

1 4 1

1 5 4

2 3 1

3 4 3

输出例子:

3 3 5

-->

示例1

输入

5 6 3

2 4 5

1 2 4

1 3 1

1 4 1

1 5 4

2 3 1

3 4 3

输出

3 3 5

 #include<iostream>

 #include<cmath>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define maxn 200005

 #define mem(a,b) memset(a,b,sizeof(a))

 typedef long long ll;

 const ll INF=0x3f3f3f3f3f3f3f3f;

 using namespace std;

 vector<pair<int,ll> >ve[maxn];

 int n,p;

 int a[maxn],bel[maxn];///离哪个大都会最近

 ll dis[maxn];

 int vis[maxn];

 ll ans[maxn];///求离自己最近的大都会的距离

 struct sair{

     int pos;

     ll len;

     friend bool operator<(sair a,sair b){

         return a.len>b.len;

     }

 };

 void Dijstra(){

     for(int i=;i<=n;i++){

         dis[i]=INF;

         ans[i]=INF;

         vis[i]=;

     }

     sair s,e;

     int pos;

     ll len;

     priority_queue<sair>Q;

     for(int i=;i<=p;i++){

         s.len=,s.pos=a[i];

         Q.push(s);

         dis[a[i]]=;

         bel[a[i]]=a[i];

     }

     while(!Q.empty()){

         s=Q.top();

         Q.pop();

         if(!vis[s.pos]){

             vis[s.pos]=;

             for(int i=;i<ve[s.pos].size();i++){

                 pos=ve[s.pos][i].first;

                 len=ve[s.pos][i].second;

                 if(dis[pos]>dis[s.pos]+len){

                     dis[pos]=dis[s.pos]+len;

                     bel[pos]=bel[s.pos];

                     e.len=dis[pos];

                     e.pos=pos;

                     Q.push(e);

                 }

                 else if(bel[pos]!=bel[s.pos]){

                     ///当两个城市属于不同的大都会时，A地到B地的最近距离为A地到K地再到B地的距离

                     ans[bel[pos]]=min(ans[bel[pos]],dis[pos]+dis[s.pos]+len);

                     ans[bel[s.pos]]=min(ans[bel[s.pos]],dis[pos]+dis[s.pos]+len);

                 }

             }

         }

     }

 }

 int main(){

     std::ios::sync_with_stdio(false);

     int m;

     cin>>n>>m>>p;

     for(int i=;i<=p;i++){

         cin>>a[i];

     }

     int aa,bb,vv;

     while(m--){

         cin>>aa>>bb>>vv;

         ve[aa].push_back(make_pair(bb,vv));

         ve[bb].push_back(make_pair(aa,vv));

     }

     Dijstra();

     for(int i=;i<=p;i++){

         if(i!=){

             cout<<" ";

         }

         cout<<ans[a[i]];

     }

     cout<<endl;

 }