luogu P1613 跑路

一开始看这道题时，发现是最短路，可是搜的又是倍增的题无可分说这是倍增+最短路

但是Dijkstra，SPFA我又不熟，可是看了数据范围心中萌生一种用Floyd做的方法

不扯了

先设一个三维bool数组是用来表示是否i到j之间有一条长度2^k的边

再设一个二维int数组是用来存时间的，再把n，m定上（定义完成）

如果说，bool数组f[i][j][k]中任意一组变为true，那么我们就可以让a[i][j]=1，表示i到j之间这一秒可以到达

那为什么不能直接在Floyd中判断ijk相等呢？因为题目中存在着环的情况，所以不行

预处理的时候最外层枚举的K，应该判断f[i][k][K-1]和f[k][j][K-1]，让f[i][j][K]=1 否则会出现没有那么多边但是a变成1的情况

本蒟蒻代码，勿喷

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
int u,v;
int a[N][N];
bool f[N][N][N];
int main()
{
    memset(a,0x3f3f3f,sizeof(a));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        f[u][v][0]=1;
        if(u==v)
            a[u][v]=0;
        else a[u][v]=1;
    }
    for(int s=1;s<=20;s++)
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(f[i][k][s-1] && f[k][j][s-1])
    {
        f[i][j][s]=1;
        if(i==j)
            a[i][j]=0;
        else a[i][j]=1;
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
    cout<<a[1][n];
    return 0;
}