CodeForces - 1442C Graph Transpositions（分层图）

传送门：CodeForces - 1442C

思路分析

可以发现，当$2$操作大于$20$次的时候，代价比$m$次$1$操作还大，对于前$20$次$2$操作，可以跑$20$层分层图
对于$20$次以上的部分，要让$2$操作尽可能的少，建两层图，一层正向一层反向，双边权$(0/1,1/0)$分别表示$1$操作和$2$操作

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 2e5+10;

ll qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n&1) res = res * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return res;
}

struct node {
    int u,fir,sec;
    bool operator < (const node &A) const {
        if(sec>20 || A.sec>20) {
            if(sec!=A.sec) return sec > A.sec;
            return fir > A.fir;
        }
        return fir+(1<<sec)-1 > A.fir+(1<<A.sec)-1;
    }
};

struct edge {
    int v,next;
    pii w;
} e[N*4];

int cnt,head[N*2],vis[N*2][24];
int n,m;

void add(int u,int v,int fir,int sec) {
    e[++cnt].v = v;
    e[cnt].w.fi = fir;
    e[cnt].w.se = sec;
    e[cnt].next = head[u];
    head[u] = cnt;
}

node dis[N*2][24];

node dij(int s) {
    mem(dis,INF);
    dis[s][0] = {s,0,0};
    priority_queue<node>q;
    q.push({s,0,0});
    while(!q.empty()) {
        node now = q.top();
        q.pop();
        int u = now.u, fir = now.fir , sec = now.sec;
        if(vis[u][min(22LL,sec)]) continue;
        vis[u][min(22LL,sec)] = 1;
        if(u == n|| u == n+n) return now;
        for(int i = head[u]; i; i=e[i].next) {
            int v = e[i].v;
            int wfi = e[i].w.fi;
            int wse = e[i].w.se;
            int nfi = fir+wfi;
            int nse = sec+wse;
            node next = {v,nfi,nse};
            if(dis[v][min(nse,22LL)]<next) {
                dis[v][min(nse,22LL)] = next;
                q.push(next);
            }
        }
    }
}

signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int u,v;
        cin>>u>>v;
        add(u,v,1,0);
        add(v+n,u+n,1,0);
    }
    for(int i=1; i<=n; i++) {
        add(i,i+n,0,1);
        add(i+n,i,0,1);
    }

    node ans = dij(1);
    int sum = (ans.fir+qpow(2,ans.sec)-1+mod)%mod;
    cout<<sum<<endl;





    return 0;
}