题解：AT_abc395_e [ABC395E] Flip Edge

题面

问题陈述

给定一个具有

N

个顶点和

M

条边的有向图。

第

i

条边

(1 \leq i \leq M)

是从顶点

u _ i

到顶点

v _ i

的有向边。

最初，您位于顶点

1

。

您希望重复以下操作，直到到达顶点

N

：

执行以下两个操作之一：
- 沿一个方向移动，当前顶点的选定边。这会产生 $1$ 的成本。更准确地说，如果在顶点 $v$ 处，则选择顶点 $u$ ，使得存在从 $v$ 到 $u$ 的有向边。并移动到顶点 $u$ 。
- 反转所有边的方向。这会产生 $X$ 的成本。更准确地说，当且仅当在该操作之前存在从 $v$ 到 $u$ 的有向边，在此操作之后，立即存在从 $u$ 到 $v$ 的有向边。对于给定的图，通过重复这些操作，可以保证从顶点 $1$ 到达顶点 $N$ 。

查找到达顶点

N

所需的最小总成本。

数据范围

$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$1 \leq X \leq 10^9$
$1 \leq u _ i \leq N \ (1 \leq i \leq M)$
$1 \leq v _ i \leq N \ (1 \leq i \leq M)$
对于给定的图，保证可以通过所描述的操作从顶点 $1$ 到达顶点 $N$ 。
所有输入值均为整数。

思路

如果没有反边的话，就是最普通的最短路，所以这题的注意点就是如何处理反边做法：

建立分层图，第一层是原图，第二层是反边图。

那么同层图直接的边权就是1；
如果要跨层的话就要付出 $X$ 的代价；
题目就变成了最普通的最短路，答案为 $\min(dis_n,dis_2\times_n)$ 。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
const ll INF=1e18;
const int N=1e6+5;
vector<array<int,2>>g[N];
vector<ll> dijk(int n,int s=1){
	priority_queue<pll,vector<pll>,greater<pll>>q; 
	vector<int>vis(2*n+10, 0);
	vector<ll>dis(2*n+10, 1e18);
	q.push({0,s});
	dis[s]=0;
	while(!q.empty()){
		int u=q.top().second; 
		q.pop();
		if(vis[u]){
			continue;	
		}
		vis[u]=1;
		for(auto [v,w]:g[u]){
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
        }
    }
	return dis;
}
int main(){
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back({v,1});
        g[v+n].push_back({u+n,1});
    }
    for(int i=1;i<=n;i++){
        g[i].push_back({i+n,x});
        g[i+n].push_back({i,x});
    }
    auto dis=dijk(n,1);
    cout<<min(dis[n],dis[2*n])<<endl;
    return 0;
}

题解：AT_abc395_e [ABC395E] Flip Edge

文章操作

题面

问题陈述

数据范围

思路

Code

相关推荐

评论

题解：AT_abc395_e [ABC395E] Flip Edge