【最短路径生成树】ABC252 E - Road Reduction

绝地灬酷狼 2024-03-23 11:12 42阅读 0赞

[E - Road Reduction (atcoder.jp)][E - Road Reduction _atcoder.jp]

题意：

![6800b3df7f9c4635949382e38125eb02.png][]

思路：

结论：如果对一个点往外做单源最短路，那么到这个图中其他所有点的路径会构成一棵树

为什么是树，因为最短路不存在环

因此这道题最终形成的树其实就是最短路径生成树

因此只需要对1做一次单源最短路，记录路径，输出树边即可

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int Inf=1e18;
    struct ty{
    	int to,next,w;
    }edge[mxe<<2];
    struct ty2{
    	int x,dis;
    	bool operator<(const ty2&a)const{
    		return a.dis<dis;
    	}
    };
    
    priority_queue<ty2> q;
    int n,m,u,v,w,tot=0;
    int id[mxn],head[mxn],vis[mxn],dis[mxn];
    void add(int u,int v,int w,int idx){
    	id[tot]=idx;
    	edge[tot].w=w;
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    }
    void G_init(){
    	tot=0;
    	for(int i=0;i<=n;i++){
    		head[i]=-1;
    	}
    }
    void dij(){
    	memset(vis,0,sizeof(vis));
    	memset(dis,0x3f,sizeof(dis));
    	dis[1]=0;
    	q.push({1,0});
    	while(!q.empty()){
    		auto u=q.top();
    		q.pop();
    		if(vis[u.x]) continue;
    		vis[u.x]=1;
    		for(int i=head[u.x];~i;i=edge[i].next){
    			if(dis[edge[i].to]>dis[u.x]+edge[i].w){
    				dis[edge[i].to]=dis[u.x]+edge[i].w;
    				q.push({edge[i].to,dis[edge[i].to]});
    			}
    		}
    	}
    }
    void solve(){
    	cin>>n>>m;
    	G_init();
    	for(int i=1;i<=m;i++){
    		cin>>u>>v>>w;
    		add(u,v,w,i);
    		add(v,u,w,i);
    	}
    	dij();
    	vector<int> v;
    	for(int x=2;x<=n;x++){
    		for(int i=head[x];~i;i=edge[i].next){
    			if(dis[x]==dis[edge[i].to]+edge[i].w){
    				v.push_back(id[i]);
    				break;
    			}
    		}
    	}
    	for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Road Reduction _atcoder.jp]: https://atcoder.jp/contests/abc252/tasks/abc252_e
[6800b3df7f9c4635949382e38125eb02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/c8eb5ba777e54df99d80fa60593d9750.png