题目分析:
题面给出每一步可以走2^k步,k为任意正整数。这很明显是倍增。
而简单的最短路无法解决这个问题,因此考虑图上倍增dp。
设f[i][j][q](bool)表示是否存在一条从i到j长度为2^q的路径。
g[i][j]存储从i到j的最小步数和
考虑初始化,
对于每一个输入的有向边(a,b),f[a][b][0]=1,g[a][b]=1
考虑状态转移:
若f[i][k][q-1]1&&f[k][j][q-1]1,可以一次走完两条路径,
故f[i][j][q]=1,g[i][j]=1。
Code
写法类似Floyd,二者共同点是寻找中转点完成转移。
#include<bits/stdc++.h>
using namespace std;
const long long INF=1e9+7;
int n,m,a,b;
long long g[55][65];
bool f[55][55][66];
long long getmin(long long a,long long b)
{
if(a>=b) return b;
else return a;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,INF,sizeof(g));
for(int i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
f[a][b][0]=1;
g[a][b]=1;
}
for(int q=1;q<=64;++q)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
for(int k=1;k<=n;++k)
{
if(f[i][k][q-1]&&f[k][j][q-1])
{
f[i][j][q]=1;
g[i][j]=1;
}
}
}
}
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
g[i][j]=getmin(g[i][j],g[i][k]+g[k][j]);
printf("%lld",g[1][n]);
return 0;
}