解题思路
小明所跑的路径，可以分成几段，每一段长为
2
t
2^t
2t，
所以关键在于确定任意点对
(
i
,
j
)
(i, j)
(i,j) 点之间是否存在
2
t
2^t
2t 的路径。
由于要计算所有点对之间的路径，所以用 Floyd 算法。
1、 计算出一个新图，初始化所有节点间的距离为无穷大。
2、若点对
(
i
,
j
)
(i, j)
(i,j) 之间的存在长
2
t
2^t
2t 的路径，把
(
i
,
j
)
(i, j)
(i,j) 的边长 mp[i][j] 赋值为 1 ，即从点
i
i
i到点
j
j
j存在一条长度为
2
t
2^t
2t的路径，使得小明可以1秒到达。
3、在这个新图上，求 1 到 n 的最短路径就是答案。
计算长度为 2^t 的路径：可以根据倍增的原理，有
2
t
=
2
t
−
1
+
2
t
−
1
2^t = 2^{t-1} +2^{t-1}
2t=2t−1+2t−1。
用
p
[
i
]
[
j
]
[
t
]
=
T
r
u
e
p[i][j][t] = True
p[i][j][t]=True 表示 i 、 j 之间有一条长
2
t
2^t
2t 的路径，
根据 Floyd 算法的思路，路径通过一个中转点
k
k
k，有
p
[
i
]
[
j
]
[
t
]
=
p
[
i
]
[
k
]
[
t
−
1
]
+
p
[
k
]
[
j
]
[
t
−
1
]
p[i][j][t]= p[i][k][t-1]+ p[k][j][t-1]
p[i][j][t]=p[i][k][t−1]+p[k][j][t−1]。
利用倍增原理计算新图 mp[]，复杂度 O(n^3)。在新图 mp[] 上计算最短路。文章来源地址https://www.toymoban.com/news/detail-549915.html
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-1
mp[u][v] = 1
p[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] = True
mp[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])
文章来源：https://www.toymoban.com/news/detail-549915.html
到了这里，关于简单图论：指数移动的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
