专栏文章

题解：AT_abc395_e [ABC395E] Flip Edge

LLovely_yhb
AT_abc395_e题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miq3eo77
此快照首次捕获于
2025/12/03 22:18
3 个月前
此快照最后确认于
2025/12/03 22:18
3 个月前
查看原文

题意

给定一个有向图，可以花 xx 的代价把边反转，花 11 的代价走一条边。
问从 11 到 nn 的最小代价。

思路

分层图最短路练手题。
一共两层图，一层正图，一层反图。在两层之间连一条权值为 xx 的双向边。然后跑 dijkstra 即可。
有可能是到反转层的终点最短，也有可能是到原层的终点最短，所以答案应该是二者间取 min⁡\min。
记得开 long long。

AC Code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,x,u,v,dis[N];
vector<pair<int,int> > to[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
signed main() {
	cin>>n>>m>>x;
	int tot=2*n;
	for(int i=0; i<m; i++) {
		cin>>u>>v;
		int u0=2*(u-1),v0=2*(v-1);
		to[u0].push_back({v0,1});
		int u1=2*(u-1)+1,v1=2*(v-1)+1;
		to[v1].push_back({u1,1});
	}
	for(int v=1; v<=n; v++) {
		int s0=2*(v-1),s1=s0+1;
		to[s0].push_back({s1,x});
		to[s1].push_back({s0,x});
	}
	memset(dis,0x3f,sizeof dis);
	dis[0]=0;
	q.push({0,0});
	while(!q.empty()) {
		auto[d,u]=q.top();
		q.pop();
		if(d!=dis[u]) continue;
		for(auto[v,w]:to[u]) {
			if(dis[v]>d+w) {
				dis[v]=d+w;
				q.push({dis[v],v});
			}
		}
	}
	cout<<min(dis[2*(n-1)],dis[2*(n-1)+1]);
	return 0;
}

评论

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

正在加载评论...