题解：AT_abc395_e [ABC395E] Flip Edge

· · 题解

本蒟蒻第一次 abc 场切 T5，写篇题解纪念一下。

思路

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

代码

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