题解：AT_abc395_e [ABC395E] Flip Edge

ZZ0520 · 2025-03-02 16:22:06 · 个人记录

题面

问题陈述

给定一个具有 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

#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;
}