Metropolis(多源点最短路)

Metropolis

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

题目描述

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

输入描述:

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

⁵

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

$x_1\sim x_p$

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

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

,b

,l

表示一条连接a

和b

，长度为l

的道路 (1 ≤ a

,b

≤ n,1 ≤ l

≤ 10

⁹

)。
保证图是连通的。

输出描述:

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

的答案。

示例1

输入

输出

3 3 5

 1 #include<iostream>
 2 #include<cmath>
 3 #include<vector>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<queue>
 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<pair<int,ll> >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<sair>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<ve[s.pos].size();i++){
48                 pos=ve[s.pos][i].first;
49                 len=ve[s.pos][i].second;
50                 if(dis[pos]>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<<ans[a[i]];
88     }
89     cout<<endl;
90 }

View Code