传送门

题目理解与强调

给定一个有向图，共有 $n$ 个点和 $m$ 条边，存在自环的情况，每条边的长度都为 $1$ 。与一般题目不同的是，每走一步会走过 $2^k$ 个单位长度（ $k$ 为任意自然数），我们要找的是从点 $1$ 到点 $n$ 中所有路径中需要步数最少的一条。

题解

排除错误算法

第一个想到的方法一定是找到从 $1$ 到 $n$ 的最短路，将最短路的长度转化为二进制，计算其中 $1$ 的个数。

但是很明显，这个算法是错误的，样例都过不了，但是我还是尝试了一下，拿到了 $30\text{pts}$ 。

[collapse title="错误算法代码" color="blue"]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define int128 __int128
#define uint128 unsigned __int128
#define Ld long double
#define reg register
#define space putchar(' ')
#define enter putchar('\n')
#define PI 3.14159265358979323846
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 1000010
namespace Fast{
    template<typename T>inline void read(T &x){
        x=0;bool f=false;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
        while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(f)x=~x+1;
    }
    template<typename T>inline void print(T x){
        int s[65],top=0;
        if(x<0)putchar('-'),x=~x+1;
        while(x)s[++top]=x%10,x/=10;
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
    template<typename T,typename...Args>inline void read(T &x,Args&...others){
        read(x),read(others...);
    }
    template<typename T,typename...Args>inline void print(T x,Args...others){
        print(x),space,print(others...);
    }
    const double eps=1e-7;
    template<typename T>inline T Abs(T x){return x>0?x:-x;}
    template<typename T>inline T Max(T x,T y){return x>y?x:y;}
    template<typename T>inline T Min(T x,T y){return x<y?x:y;}
    template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
    template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
    template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
    template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
    template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
}
using namespace Fast;
struct Node{
    int nxt,to;
}e[200010];
typedef pair<int,int> pa;
priority_queue<pa,vector<pa>,greater<pa> >q;
int g[200010],nxt,dis[200010],vis[200010],ans,n,m,p;
void add(int x,int y){
    e[++nxt].to=y;
    e[nxt].nxt=g[x];
    g[x]=nxt;
}
void dij(int S){
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    dis[S]=0;
    q.push(pa(0,S));
    while(!q.empty()){
        int x=q.top().se;
        if(vis[x]==1){
            continue;
            p=1;
        }
        vis[x]=1;
        q.pop();
        for(int k=g[x];k;k=e[k].nxt){
            int y=e[k].to;
            if(dis[y]>dis[x]+1){
                dis[y]=dis[x]+1;
                q.push(pa(dis[y],y));
            }
        }
    }
    return;
}
int main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    read(n,m);
    for(int i=1;i<=m;i++){
        int u,v;
        read(u,v);
        add(u,v);
        add(v,u);
    }
    dij(1);
    while(dis[n]!=0){
        if(dis[n]%2==1)
            ans++;
        dis[n]>>=1;
    }
    if(p==1)
        ans=1;//妄图挣扎一下 
    print(ans);
    return 0;
}

[/collapse]

为什么？因为最短路不一定是二进制数字中 $1$ 的个数最少的方案，例如：我可以通过多次走自环的方式，将步数归为 $1$ ，我也可以走一个较长的路径，但是这一种方案所需要的距离最少。故：最短距离 $\neq$ 最小步数 。

正确方法探讨

本题重点在于善用倍增算法，他的计步方式很特殊，每一步可以跑 $2^k$ 的距离，那么判断一个点 $x$ 到一个点 $y$ 能否只需要走一步就完成，只需要找到一个点 $v$ ，判断是否存在 $d_{x,v}$ （ $d_{i,j}$ 表示由 $i$ 到 $j$ 的一条路径实际长度）是否等于 $d_{v,y}$ 等于 $2^{k-1}$

这样，从 $x$ 点到 $y$ 点的实际距离就可以为 $2^k$ ，只需要一步就可以到。

那么我们规定一个动态规划数组 $dp_{i,j,k}$ ，表示从点 $i$ 到点 $j$ 中是否存在一条实际距离为 $2^k$ 的一条路径。根据上述原理很容易地，我们得到如下代码：

if(dp[i][j][k-1]&dp[j][c][k-1]==1)
{
    dp[i][c][k]=1;
    dis[i][c]=1;
}

其中的 $dis$ 数组是用来求最短路用的， $dis_{i,j}$ 表示点 $i$ 到点 $j$ 的最少步数。我们将枚举所有起始点、中间点和终点，将所有距离更新即可，当然，第 $dis$ 的三维数组需要从小到大枚举。

由于数据范围很小，又因为我们使用了邻接矩阵存图，所以直接使用 Floyd 算法求 $dis$ 最短路（最小步数）。

参考代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define int128 __int128
#define uint128 unsigned __int128
#define Ld long double
#define reg register
#define space putchar(' ')
#define enter putchar('\n')
#define PI 3.14159265358979323846
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<endl
#define pri(x,lo) {cerr<<#x<<"={";for (int ol=0;ol<=lo;ol++)cerr<<x[ol]<<",";cerr<<"}"<<endl;}
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 1000010
namespace Fast{
    template<typename T>inline void read(T &x){
        x=0;bool f=false;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=true;c=getchar();}
        while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(f)x=~x+1;
    }
    template<typename T>inline void print(T x){
        int s[65],top=0;
        if(x<0)putchar('-'),x=~x+1;
        while(x)s[++top]=x%10,x/=10;
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
    template<typename T,typename...Args>inline void read(T &x,Args&...others){
        read(x),read(others...);
    }
    template<typename T,typename...Args>inline void print(T x,Args...others){
        print(x),space,print(others...);
    }
    const double eps=1e-7;
    template<typename T>inline T Abs(T x){return x>0?x:-x;}
    template<typename T>inline T Max(T x,T y){return x>y?x:y;}
    template<typename T>inline T Min(T x,T y){return x<y?x:y;}
    template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
    template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
    template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
    template<typename T>inline void addmod(T &x,T p){if(x>=p)x-=p;}
    template<typename T>inline void submod(T &x,T p){if(x<0)x+=p;}
}
using namespace Fast;
int n,m,dis[101][101];
bool dp[101][101][101];
int main(){
    // freopen("a.in","r",stdin);
    // freopen("a.out","w",stdout);
    read(n,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;
        read(u,v);
        dis[u][v]=1;
        dp[u][v][0]=1;
    }
    for(int k=1;k<=64;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int c=1;c<=n;c++){
                    if(dp[i][j][k-1]&dp[j][c][k-1]==1)
                    {
                        dp[i][c][k]=1;
                        dis[i][c]=1;
                    }
                }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=Min(dis[i][k]+dis[k][j],dis[i][j]);
            }
        }
    }
    print(dis[1][n]);
    return 0;
}