解题思路

小明所跑的路径，可以分成几段，每一段长为 $2^t$，
所以关键在于确定任意点对 $(i,j)$ 点之间是否存在 $2^t$ 的路径。
由于要计算所有点对之间的路径，所以用 Floyd 算法。
1、 计算出一个新图，初始化所有节点间的距离为无穷大。
2、若点对 $(i,j)$ 之间的存在长 $2^t$ 的路径，把 $(i,j)$ 的边长 mp[i][j] 赋值为 1 ，即从点$i$到点$j$存在一条长度为$2^t$的路径，使得小明可以1秒到达。
3、在这个新图上，求 1 到 n 的最短路径就是答案。
计算长度为 2^t 的路径：可以根据倍增的原理，有 $2^t=2^{t-1}+2^{t-1}$。
用 $p[i][j][t]=True$ 表示 i 、 j 之间有一条长 $2^t$ 的路径，
根据 Floyd 算法的思路，路径通过一个中转点 $k$，有$p[i][j][t]=p[i][k][t-1]+p[k][j][t-1]$。
利用倍增原理计算新图 mp[]，复杂度 O(n^3)。在新图 mp[] 上计算最短路。

AC_Code

# -*- coding: utf-8 -*-
# @Author : BYW-yuwei
# @Software: python3.8.6
N = 55
p = [[[False for _ in range(33)] for _ in range(N)] for _ in range(N)]
mp = [[float('inf') for _ in range(N)] for _ in range(N)]
n,m = map(int,input().split())
for i in range(m):u,v = map(int,input().split())u,v = u-1,v-1mp[u][v] = 1p[u][v][0] = True
for t in range(1,33):for k in range(n):for i in range(n):for j in range(n):if p[i][k][t-1] and p[k][j][t-1]:p[i][j][t] = Truemp[i][j] = 1
for k in range(n):for i in range(n):for j in range(n):mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j])
print(mp[0][n-1])