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

_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 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=0;i<=n;i++){
        dis[i]=INF;
        ans[i]=INF;
        vis[i]=0;
    }
    sair s,e;
    int pos;
    ll len;
    priority_queue<sair>Q;
    for(int i=1;i<=p;i++){
        s.len=0,s.pos=a[i];
        Q.push(s);
        dis[a[i]]=0;
        bel[a[i]]=a[i];
    }
    while(!Q.empty()){
        s=Q.top();
        Q.pop();
        if(!vis[s.pos]){
            vis[s.pos]=1;
            for(int i=0;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=1;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=1;i<=p;i++){
        if(i!=1){
            cout<<" ";
        }
        cout<<ans[a[i]];
    }
    cout<<endl;
}