https://ac.nowcoder.com/acm/contest/203/I?&headNav=www

 

题目描述

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

输入描述:

第一行三个整数n,m,p (1 ≤ n,m ≤ 2*105,2 ≤ p ≤ n)，第二行p个整数x1∼xpx1∼xp表示大都会的编号 (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

 

记录每个点是从哪个大都会扩展来的，将所有大都会放入堆，跑多源最短路，d[u]值为u距任意大都会的最短路。当一个扩展到的点与已扩展的点相连时，就更新答案。注意开long long。

下面是理解：

在图G=(V,E)上运行Dijkstra,对于任意结点u，当u出堆时，一定u已经找到了最短路(即d[u]是正确的)。每个点出堆一次，对于任意一条边u<--->v，会被访问2次，因为u，v出堆时均会尝试进行松弛，该边在第二次被访问时，必有两点均以被扩展，即均找到了最短路，这样的话，这条边就有可能是在u，v分别的来源大都会之间的最短路上，u，v是这条路的中间结点。这时就更新答案。

为什么这样做是正确的呢？

1.首先，最起码每个大都会的来源都是其本身

2.对于任意以找到来源大都会的结点u，当存在u<--->v时，不管v属于哪个大都会，第二次访问到该边时，都会更新u和v所属的大都会的所求值。

3.综合上述两点，对于任意的已找到所属大都会s的点u的集合，对于其中任意一点，其所有的连边都会被访问两次，故一定能比较到所有的s所求的可能取到的值。

4.在第3点的基础上，需要注意必须把u，v所属大都会（设为s，t）都更新到，不能只更新s，因为u<--->v只访问2次，第一次访问该边只是从v松弛，没有改变t的所求值，当然，更没有改变s的所求值，所以第二次必须同时改变s，t的所求值。

经上述推理，可知该方法的正确性。

 

 

#include<bits/stdc++.h>
using namespace std;
#define maxn 200000+10

struct Edge{
	int from,to,dist;
};
struct HeapNode{
	int u;long long d;
	bool operator < (const HeapNode& rhs)const{
		return d>rhs.d;
	}
};
int n,m,p,x[maxn];
vector<Edge> edges;
vector<int> G[maxn];
bool vis[maxn];
long long d[maxn],ans[maxn];
int fa[maxn];

void AddEdge(int f,int t,int d)
{
	edges.push_back((Edge){f,t,d});
	G[f].push_back(edges.size()-1);
}
void dijkstra()
{
	priority_queue<HeapNode> Q;
	for(int i=1;i<=n;i++)d[i]=(1LL<<50);
	for(int i=1;i<=p;i++)
	{
		d[x[i]]=0;
		fa[x[i]]=x[i];
		Q.push((HeapNode){x[i],0});
	}
	while(!Q.empty())
	{
		HeapNode x=Q.top();
		Q.pop();
		int u=x.u;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++)
		{
			Edge& e=edges[G[u][i]];
			if(d[e.to]>d[u]+e.dist)
			{
				d[e.to]=d[u]+e.dist;
				fa[e.to]=fa[u];
				Q.push((HeapNode){e.to,d[e.to]});
			}
			else if(vis[e.to]&&fa[u]!=fa[e.to])
			{   
				ans[fa[u]]=min(ans[fa[u]],d[u]+d[e.to]+e.dist);
				ans[fa[e.to]]=min(ans[fa[e.to]],d[u]+d[e.to]+e.dist);
			}
		}
	}	
}

int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>m>>p;
	for(int i=1;i<=p;i++)cin>>x[i];
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		AddEdge(x,y,z);
		AddEdge(y,x,z);
	}
	fill(ans,ans+maxn,1LL<<50);
	dijkstra();
	for(int i=1;i<=p;i++)cout<<ans[x[i]]<<" ";
	cout<<"\n";
	return 0;
}