题解：AT_abc395_e [ABC395E] Flip Edge

Lovely_yhb · 2025-03-02 08:29:36 · 题解

题意

给定一个有向图，可以花 x 的代价把边反转，花 1 的代价走一条边。

问从 1 到 n 的最小代价。

思路

分层图最短路练手题。

一共两层图，一层正图，一层反图。在两层之间连一条权值为 x 的双向边。然后跑 dijkstra 即可。

有可能是到反转层的终点最短，也有可能是到原层的终点最短，所以答案应该是二者间取 \min。

记得开 long long。

AC Code

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