Metropolis

题目描述

魔方国有n座城市，编号为

。城市之间通过n-1条无向道路连接，形成一个树形结构。

在若干年之后，其中p座城市发展成了大都会，道路的数量也增加到了m条。

大都会之间经常有贸易往来，因此，对于每座大都会，请你求出它到离它最近的其它大都会的距离。

输入描述:

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

⁵

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

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

_i

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

_i

,b

_i

,l

_i

表示一条连接a

_i

和b

_i

，长度为l

_i

的道路 (1 ≤ a

_i

,b

_i 

≤ n,1 ≤ l

_i 

≤ 10

⁹

)。 保证图是连通的。

输出描述:

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

_i

的答案。

示例1

输入

5 6 32 4 51 2 41 3 11 4 11 5 42 3 13 4 3

输出

3 3 5

1 #include
           
             2 #include
            
              3 #include
             
               4 #include
              
                5 #include
               
                 6 #include
                
                  7 #define maxn 200005 8 #define mem(a,b) memset(a,b,sizeof(a)) 9 typedef long long ll;10 const ll INF=0x3f3f3f3f3f3f3f3f;11 using namespace std;12 13 vector
                 
                  
                    >ve[maxn];14 int n,p;15 int a[maxn],bel[maxn];///离哪个大都会最近16 ll dis[maxn];17 int vis[maxn];18 ll ans[maxn];///求离自己最近的大都会的距离19 struct sair{20 int pos;21 ll len;22 friend bool operator<(sair a,sair b){23 return a.len>b.len;24 }25 };26 void Dijstra(){27 for(int i=0;i<=n;i++){28 dis[i]=INF;29 ans[i]=INF;30 vis[i]=0;31 }32 sair s,e;33 int pos;34 ll len;35 priority_queue
                   
                    Q;36 for(int i=1;i<=p;i++){37 s.len=0,s.pos=a[i];38 Q.push(s);39 dis[a[i]]=0;40 bel[a[i]]=a[i];41 }42 while(!Q.empty()){43 s=Q.top();44 Q.pop();45 if(!vis[s.pos]){46 vis[s.pos]=1;47 for(int i=0;i
                    
                     dis[s.pos]+len){51 dis[pos]=dis[s.pos]+len;52 bel[pos]=bel[s.pos];53 e.len=dis[pos];54 e.pos=pos;55 Q.push(e);56 }57 else if(bel[pos]!=bel[s.pos]){58 ///当两个城市属于不同的大都会时，A地到B地的最近距离为A地到K地再到B地的距离59 ans[bel[pos]]=min(ans[bel[pos]],dis[pos]+dis[s.pos]+len);60 ans[bel[s.pos]]=min(ans[bel[s.pos]],dis[pos]+dis[s.pos]+len);61 }62 }63 }64 }65 66 67 }68 69 int main(){70 std::ios::sync_with_stdio(false);71 int m;72 cin>>n>>m>>p;73 for(int i=1;i<=p;i++){74 cin>>a[i];75 }76 int aa,bb,vv;77 while(m--){78 cin>>aa>>bb>>vv;79 ve[aa].push_back(make_pair(bb,vv));80 ve[bb].push_back(make_pair(aa,vv));81 }82 Dijstra();83 for(int i=1;i<=p;i++){84 if(i!=1){85 cout<<" ";86 }87 cout<