题目概述

CF1442

解题报告

首先有个基础想法：$dis_{i,j}$ 表示走到 $i$ ，反转了 $j$ 次的最短路，那么答案就是 $\min\{dis_{n,j}+2^j-1\}$ 。

但是反转次数可能很大，不过，我们发现反转操作的代价增长是指数级的，也就是说，在 $20$ 次反转之后，假设 $k$ 次反转是可行的，那么 $k+1$ 次反转一定是不优的，因为 $2^{k}>n$ ，边数的影响可以忽略。

因此我们先求一次反转次数的最短路，如果最少的反转次数 $\ge 20$ ，那么肯定选用最少的反转次数对应的边数最短路，否则我们按照基础想法进行最短路，只不过 $j$ 最大只有 $20$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxm=400000,maxk=20,MOD=998244353;

int n,m,dis[maxn+5][maxk+5],dep[maxn+5][2],ans;
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5],w[maxm+5];
int que[maxn*maxk+5],num[maxn*maxk+5];bool vis[maxn+5][maxk+5];

#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
#define AM(x) ((x)+1>=maxn*maxk?0:(x)+1)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y,0),Add(y,x,1);
    for (int i=1;i<=n;i++) dis[i][0]=dis[i][1]=dep[i][0]=dep[i][1]=1e9;
    int Head=0,Tail=0;que[++Tail]=1;dis[1][0]=0;dep[1][0]=0;vis[1][0]=true;
    while (Head!=Tail){
        int x=que[Head=AM(Head)];vis[x][0]=false;
        for (int j=lnk[x];j;j=nxt[j]){
            int u=son[j],k=w[j];
            for (int t=0;t<2;t++)
                if (dis[x][t]+(t!=k)<dis[u][k] || dis[x][t]+(t!=k)==dis[u][k] && dep[x][t]+1<dep[u][k]){
                    dis[u][k]=dis[x][t]+(t!=k);dep[u][k]=dep[x][t]+1;
                    if (!vis[u][0]) que[Tail=AM(Tail)]=u,vis[u][0]=true;
                }
        }
    }
    if (min(dis[n][0],dis[n][1])>=20){
        if (dis[n][0]<dis[n][1]) printf("%d\n",(Pow(2,dis[n][0])-1+dep[n][0])%MOD); else
        if (dis[n][1]<dis[n][0]) printf("%d\n",(Pow(2,dis[n][1])-1+dep[n][1])%MOD); else
        printf("%d\n",(Pow(2,dis[n][0])-1+min(dep[n][0],dep[n][1]))%MOD);
        return 0;
    }
    for (int i=1;i<=n;i++) for (int j=0;j<=20;j++) dis[i][j]=1e9;
    Head=0;Tail=0;que[++Tail]=1;num[Tail]=0;dis[1][0]=0;vis[1][0]=true;
    while (Head!=Tail){
        int x=que[Head=AM(Head)],y=num[Head];vis[x][y]=false;
        for (int j=lnk[x];j;j=nxt[j]){
            int u=son[j],k=w[j],f=(y&1)!=k;
            if (y+f>20) continue;
            if (dis[x][y]+1<dis[u][y+f]){
                dis[u][y+f]=dis[x][y]+1;
                if (!vis[u][y+f]) que[Tail=AM(Tail)]=u,num[Tail]=y+f,vis[u][y+f]=true;
            }
        }
    }
    ans=1e9;
    for (int i=0;i<=20;i++) if (dis[n][i]+(1<<i)-1<ans) ans=dis[n][i]+(1<<i)-1;
    printf("%d\n",ans);
    return 0;
}