https://www.acwing.com/problem/content/description/347/
Floyd有着天然倍增的性质
如果我要求恰好经过k条边从i到j的最短路的话 Floyd+倍增 复杂度log(k)*n*n*n
我们初始化g数组表示从i到j只经过一条路径的最短距离
那么g[i][i]就不能初始化0了,而是正无穷
将只经过一条路径的最短路数组g做一次Floyd,如下
那么做完之后g就表示从i到j恰好用了2条路径的最短路
同理2->4 4->8
为什么要用到temp呢?
答案就是如果i到j恰好用2条路径没有解的话,temp就是正无穷,那么最后g[i][j]就是正无穷
如果不用temp的话最后g[i][j]表示的是只经过一条路径的最短路
static int temp[N][N];
memset(temp, 0x3f, sizeof temp);
for (int k = 1; k <= cnt; k++)
for (int i = 1; i <= cnt; i++)
for (int j = 1; j <= cnt; j++)
temp[i][j] = min(temp[i][j], g[i][k] + g[k][j]);
定义答案数组为res
res最初表示从i到j经过0条路的最短路
那么res[i][i]=0,其他的都为正无穷
然后二进制分解k
加入k=5;那么二进制就是101
那么当g表示一条路,g表示4条路的时候,用g去更新答案数组res
最后答案从i到j恰好经过k条路径的最短路就是res[i][j]