题解 Luogu P2934 [USACO09JAN]Safe Travel G

题意

给定 \(n\) 个点 \(m\) 条边的无向连通图,第 \(i\) 条边 \((u_i,v_i)\) 的权值为 \(t_i\),保证 \(1\) 到每个点的最短路唯一。

对于每个点 \(x\),求出从 \(1\) 出发,在不走 \(1\) 到 \(x\) 的最短路上最后一条边的情况下,\(1\) 到 \(x\) 的最短路径。

\(1 \leq n \leq 10^5, 1\leq m \leq 2 \times 10^5, 1 \leq t \leq 1000\)

题解

因为最短路唯一,所以可以建出最短路径树。

考虑一条非树边 \((u,v)\),加上它之后会形成环,其最多只可能能对环上,即路径 \(u \to \operatorname{lca}(u,v) \to v\) 上(不包含 \(\operatorname{lca}(u,v)\))所有点造成贡献。

令 \(d_i\) 表示 \(1\) 到 \(i\) 的最短路。如果边 \((u,v)\) 的权值为 \(w\) 且该边能对 \(x\) 造成贡献,那么通过边 \((u,v)\),\(1\) 到达 \(x\) 的最短路径为 \(d_u+d_v-d_x+w\)。注意到对于 \(d_x\) 只和 \(x\) 有关,\(d_u+d_v+w\) 只与边 \((u,v)\) 有关。

接下来有两个做法:

  • 做法一

    观察到,对于每条边,其能够造成贡献的点是两条链,树链剖分 + 线段树区间覆盖单点查询最小值。

    时间复杂度 \(O(m \log^2n)\)。

  • 做法二

    对于所有边 \((u,v)\),按照 \(d_u+d_v+w\) 对这些边进行排序,暴力更新。

    因为排了序,所以每个点只会被更新一次(后面的多次更新没有用)。更新完之后用并查集把这些点缩成一个,避免下一次修改。

    时间复杂度 \(O(m \log n+n)\)。

    # include <bits/stdc++.h>
    
    const int N=200010,INF=0x3f3f3f3f;
    
    struct Edge{
    	int to,next,v;
    }edge[N<<1];
    struct Node{
    	int id,w;
    	bool operator < (const Node &rhs) const{
    		return w>rhs.w;
    	}
    };
    std::priority_queue <Node> q;
    struct AnoEdge{
    	int u,v,w;
    	bool operator < (const AnoEdge &rhs) const{
    		return w<rhs.w;
    	}
    }anoedge[N];
    int anosum;
    int head[N],sum;
    int dis[N];
    bool c[N],vis[N];
    int n,m;
    int ans[N];
    int pre[N],eid[N],f[N],depth[N];
    int eu[N],ev[N],ew[N];
    
    inline int read(void){
    	int res,f=1;
    	char c;
    	while((c=getchar())<'0'||c>'9')
    		if(c=='-')f=-1;
    	res=c-48;
    	while((c=getchar())>='0'&&c<='9')
    		res=res*10+c-48;
    	return res*f;
    }
    inline void add(int x,int y,int v){
    	edge[++sum].to=y,edge[sum].next=head[x],edge[sum].v=v,head[x]=sum;
    	return;
    }
    inline void Dijkstra(void){
    	memset(dis,INF,sizeof(dis));
    	dis[1]=0,q.push((Node){1,0});
    	while(!q.empty()){
    		int i=q.top().id;
    		q.pop();
    		if(c[i])
    			continue;
    		c[i]=true;
    		for(int j=head[i];j;j=edge[j].next){
    			int to=edge[j].to;
    			if(dis[to]>dis[i]+edge[j].v){
    				dis[to]=dis[i]+edge[j].v,pre[to]=i,eid[to]=j,q.push((Node){to,dis[to]});
    			}
    		} 
    	}
    	return;
    }
    inline int find(int x){
    	return (f[x]==x)?x:(f[x]=find(f[x]));
    }
    void dfs(int i){
    	depth[i]=depth[pre[i]]+1;
    	for(int j=head[i];j;j=edge[j].next){
    		int to=edge[j].to;
    		if(to!=pre[i]&&pre[to]==i)
    			dfs(to);
    	}
    	return;
    }
    int main(void){
    	n=read(),m=read();
    	for(int i=1;i<=m;++i){
    		eu[i]=read(),ev[i]=read(),ew[i]=read();
    		add(eu[i],ev[i],ew[i]),add(ev[i],eu[i],ew[i]);
    	}
    	Dijkstra();
    	for(int i=1;i<=n;++i){
    		vis[(eid[i]-1)/2+1]=true,f[i]=i,ans[i]=-1;
    	}
    	for(int i=1;i<=m;++i){
    		if(!vis[i]){
    			anoedge[++anosum].u=eu[i],anoedge[anosum].v=ev[i],anoedge[anosum].w=dis[eu[i]]+dis[ev[i]]+ew[i];
    		}
    	}
    	std::sort(anoedge+1,anoedge+1+anosum);
    	dfs(1);
    	for(int i=1;i<=anosum;++i){
    		int u=anoedge[i].u,v=anoedge[i].v;
    		u=find(u),v=find(v);
    		while(u!=v){
    			if(depth[u]<depth[v])
    				std::swap(u,v);
    			ans[u]=anoedge[i].w-dis[u];
    			f[u]=find(pre[u]),/*u 被更新了,更新 f[u], 下次路过的时候直接更新它的祖先*/u=f[u];
    		}
    	}
    	for(int i=2;i<=n;++i)
    		printf("%d\n",ans[i]);
    	return 0;
    }
    
上一篇:mysql安全更新报错You are using safe update mode and you tried to update


下一篇:php代码审计1(php.ini配置)