当前位置:网站首页>P2934 [usaco09jan] safe travel g (parallel search & shortest path tree)

P2934 [usaco09jan] safe travel g (parallel search & shortest path tree)

2021-08-10 08:44:06 wx6110fa547fd20

P2934 [USACO09JAN]Safe Travel G( Union checking set & Shortest path tree )

Ideas

The last updated edge of each node in the shortest path of a graph can form a shortest path spanning tree .

According to the subject conditions , We want to find the shortest path of each node without passing through the parent side .

Consider for the current node i i i First pass through a node of its subtree u u u, Then pass by a non tree u → v u\rightarrow v uv, And then from v → 1 v\rightarrow 1 v1.

The answer to this calculation is : d u + d v + w u , v − d i d_u+d_v+w_{u,v}-d_i du+dv+wu,vdi, Note that the first three items are related to i i i irrelevant , So we can find all non tree edges first , Then sort , Then update the answer with these edges , Which nodes can be updated for each edge ?

Obviously, it can be updated u → l c a ( u , v ) u\rightarrow lca(u,v) ulca(u,v) and v → l c a ( u , v ) v\rightarrow lca(u,v) vlca(u,v) All nodes on these two paths , barring l c a lca lca In itself . In other words, the two endpoints of this edge are not in the same subtree .

We only need to update each node once , Because the front edge must be better than the back edge after sorting .

code

// Problem: P2934 [USACO09JAN]Safe Travel G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2934
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2021-04-01 11:47:06
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+5,M=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int n,m,h[N],cnt,d[N];
int s[N];
int f[N];
int ans[N];
int find(int x){return x==s[x]?x:s[x]=find(s[x]);}
void Init(int n){
	for(int i=1;i<=n;i++) s[i]=i,ans[i]=-1;
}
struct edge{
	int to,nt,w;
}e[M<<1];
void add(int u,int v,int w){
	e[++cnt]={v,h[u],w},h[u]=cnt;
	e[++cnt]={u,h[v],w},h[v]=cnt;
}
struct node{
	int u,v,w;
}a[M],b[M];
int tot;
void dij(){
	priority_queue<PII>q;
	mst(d,0x3f);d[1]=0;
	q.push({0,1});
	while(!q.empty()){
		int u=q.top().se,l=-q.top().fi;q.pop();
		if(l>d[u]) continue;
		for(int i=h[u];i;i=e[i].nt){
			int v=e[i].to,w=e[i].w;
			if(d[v]>d[u]+w) f[v]=u,d[v]=d[u]+w,q.push({-d[v],v});
		}
	}
}
bool cmp(node a,node b){
	return a.w<b.w;
}
void fun(node &a){
	int u=a.u,v=a.v,w=a.w;
	while(find(u)!=find(v)){
		if(d[find(u)]<d[find(v)]) swap(u,v);
		ans[find(u)]=w-d[find(u)];
		u=s[find(u)]=f[find(u)];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		a[i]={u,v,w};
	}
	dij();
	for(int i=1;i<=m;i++){
		int u=a[i].u,v=a[i].v,w=d[u]+d[v]+a[i].w;
		if(f[u]!=v&&f[v]!=u) b[++tot]={u,v,w};
	}
	sort(b+1,b+tot+1,cmp);
	Init(n);
	for(int i=1;i<=tot;i++)
			fun(b[i]);
	for(int i=2;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810084311892n.html

随机推荐