专栏文章

题解：AT_abc395_e [ABC395E] Flip Edge

JJayfeather2012
AT_abc395_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq38a27
此快照首次捕获于
2025/12/03 22:13
3 个月前
此快照最后确认于
2025/12/03 22:13
3 个月前
查看原文
本蒟蒻第一次 abc 场切 T5，写篇题解纪念一下。

思路

分层图~~
不懂分层图的戳这里
一般有神奇操作的题目都是可以用分层图解的。
根据题目中将边反转方向的操作，我们建立两层图，第一层是原图，第二层是反图，再根据反转操作，将原图的每一个顶点连接一条终点为反图的此顶点，边权为 xx 的边，因为可以多次反转，反图的每一个顶点也要连接一条终点为原图的此顶点，边权为 xx 的边。
看图或许更直观：
以样例二为例：
红边为反转操作，权值为 xx。
后缀为 zz 表示原图，为 ff 表示反图。
最后跑一遍 Dijkstra 就好啦！
具体细节看代码吧！

代码

CPP
#include<bits/stdc++.h>
#define int long long
//注意要开 long long 
#define pp pair<int,int>
using namespace std;
int n,m,x,d[500005],v[500005];
vector<pp>a[500005];
//邻接表，1~n表示原图，n+1~n*2表示反图 
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>x;
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		a[u].emplace_back(make_pair(v,1));
		//原图建边 
		a[v+n].emplace_back(make_pair(u+n,1));
		//反图建边 
	}
	for(int i=1;i<=n;++i){
		a[i].emplace_back(make_pair(n+i,x));
		a[i+n].emplace_back(make_pair(i,x));
		//反转操作建边，权值为 x 
	}
	priority_queue<pp,vector<pp>,greater<pp>>q;
	q.push(make_pair(0,1));
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	while(q.size()){
		int u=q.top().second;
		q.pop();
		if(v[u])continue;
		v[u]=1;
		for(auto t:a[u]){
			int v=t.first,w=t.second;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push(make_pair(d[v],v));
			}
		}
	}
	//Dijkstra 
	cout<<min(d[n],d[n*2])<<"\n";
	//注意是取原图和反图到 n的最小值 
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...