Luogu P1613 跑路

　　Luogu在博客里的第20题！

　　这其实是一个想明白的就很简单的问题。

　　首先，我们可以否决那些直接跑最短路然后看能拆出几个2^k次方的算法。

　　其次，Floyd求最短路大家肯定都知道，但是求传递闭包的方法也是利用了Floyd。

　　所以，这道题的大致思想就是Floyd两次！

　　我们可以先把题目中给定的点先连一条权值为1的边，然后在对于所有点对之间的距离为2^k的把距离更新为1。

　　最后一次来求最短路很容易，但对于更新就有点恶心。

　　因为这里的要求边权很特殊，是2^k，所以我们用倍增可以卡过去。

　　开一个数组f[p][i][j]表示从i到j之间是否有一条长度为2^p的边（f[0][i][j]就是初始给出的边，因为2^0=1）。这样我们在用Floyd计算闭包时，如果满足f[p-1][i][k]&&f[p-1][k][j]，那么相应的f[p-1][i][j]和dis[i][j]都可以更新为1。

　　然后我就因为用了一个常量P定义数组长度，循环时却打了for (i=1;i<=P;++i) 然后炸了数组一直RE。

　　CODE

#include<cstdio>
#include<cstring>
using namespace std;
const int N=55,P=35,INF=1e9;
int dis[N][N],i,j,k,p,n,m,x,y;
bool f[P][N][N];
inline void read(int &x)
{
    x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline int min(int a,int b) { return a<b?a:b; }
int main()
{
    read(n); read(m);
    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
    dis[i][j]=INF;
    for (i=1;i<=m;++i)
    {
        read(x); read(y);
        dis[x][y]=f[0][x][y]=1;
    }
    for (p=1;p<P;++p)
    for (k=1;k<=n;++k)
    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
    {
        f[p][i][j]|=f[p-1][i][k]&&f[p-1][k][j];
        if (f[p][i][j]) dis[i][j]=1;
    }
    for (k=1;k<=n;++k)
    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    printf("%d",dis[1][n]);
    return 0;
}