题目描述
魔方国有n座城市，编号为。城市之间通过n-1条无向道路连接，形成一个树形结构。
在若干年之后，其中p座城市发展成了大都会，道路的数量也增加到了m条。
大都会之间经常有贸易往来，因此，对于每座大都会，请你求出它到离它最近的其它大都会的距离。
输入描述:
第一行三个整数n,m,p (1 ≤ n,m ≤ 2*105,2 ≤ p ≤ n)，第二行p个整数表示大都会的编号 (1≤ xi≤ n)。接下来m行每行三个整数ai,bi,li表示一条连接ai和bi，长度为li的道路 (1 ≤ ai,bi ≤ n,1 ≤ li ≤ 109)。 保证图是连通的。
输出描述:
输出一行p个整数，第i个整数表示xi的答案。
示例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
题目要求求得跟当前大都会距离最近的大都会的距离，边数在2e5，所以选择枚举每一条边，考虑每条边到最近的大都会的距离，然后加上两点之间的距离，维护一个最小值，就是当前跟大都会距离最近的大都会的距离。
维护最短路的时候，需要记录当前点距离最近的大都会的距离，若是后面的大都会扩展到此点，则应该跳过此点的计算。所以选择使用优先队列来维护，确保到达当前点的最近大都会是唯一的，然后枚举每一条边，当两点连接的大都会不是同一个点时，去维护dis[u]+dis[v]+p[j].w的最小值。
代码实现：
/*
Look at the star
Look at the shine for U
*/
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define sl(x) scanf("%lld",&x)
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
ll inv(ll b){if(b==1)return 1; return (mod-mod/b)*inv(mod%b)%mod;}
ll fpow(ll n,ll k){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%mod;n=n*n%mod;}return r;}
struct node{
int u,v,next;
ll w;
}p[N];
int head[N],vis[N],cnt,fa[N],s[N];
ll ans[N],dis[N];
struct point{
int from,to;
ll dis;
friend bool operator < (point a,point b)
{
return a.dis > b.dis;
}
};
priority_queue <point> q;
void init(int n)
{
memset(head,-1,sizeof(head[0])*(n+1));
cnt = 0;
}
void add(int u,int v,ll w)
{
p[cnt].v = v;
p[cnt].w = w;
p[cnt].next = head[u];
head[u] = cnt++;
}
void bfs()
{
while(!q.empty())
{
point t = q.top();
q.pop();
// cout<<t.from<<"***"<<endl;
if(vis[t.to]) continue;
dis[t.to] = t.dis;
vis[t.to] = 1;
fa[t.to] = t.from;
for(int i = head[t.to];~i;i = p[i].next)
{
q.push((point{t.from,p[i].v,t.dis+p[i].w}));
}
}
}
int main()
{
int n,m,i,j,k,Q,x,y;
ll w;
scanf("%d%d%d",&n,&m,&Q);
init(n);
for(i = 0;i < Q;i++)
{
scanf("%d",&s[i]);
q.push(point{s[i],s[i],0ll});
}
while(m--)
{
scanf("%d%d",&x,&y);sl(w);
add(x,y,w);
add(y,x,w);
}
bfs();
for(i = 0;i <= n;i++)
ans[i] = 1e18;
for(i = 1;i <= n;i++)
{
for(j = head[i];~j;j = p[j].next)
{
// cout<<i<<"---->"<<p[j].v<<":"<<fa[i]<<"***"<<fa[p[j].v]<<endl;
if(fa[i] != fa[p[j].v])
{
ans[fa[i]] = min(ans[fa[i]],dis[i]+dis[p[j].v]+p[j].w);
ans[fa[p[j].v]] = min(ans[fa[p[j].v]],dis[i]+dis[p[j].v]+p[j].w);
}
}
}
for(i = 0;i < Q;i++)
{
if(i) printf(" ");
printf("%lld",ans[s[i]]);
}
puts("");
}