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;
}