P1613 跑路 (最短路,倍增)

题目链接

Solution

发现 \(n\) 只有 \(50\), 可以用 \(floyd\) .

然后 \(w[i][j][l]\) 代表 \(i\) 到 \(j\) 是否存在 \(2^l\) 长的路.

四重循环,枚举即可.如果有则更新 \(dis[i][j]\) 为 \(1\) .

然后再跑 \(floyd\) 即可.

不过注意枚举 \(l\) 的这一层要大一点,到 \(50\) 左右.

Code

#include<bits/stdc++.h>

typedef int _int;

#define int long long

using namespace std;

int w[51][51][51];

int n,m,dis[51][51];

_int main()

{

    scanf("%lld%lld",&n,&m);

    memset(dis,0x3f,sizeof(dis));

    for(int i=1;i<=m;i++)

    {

        int x,y;

        scanf("%lld%lld",&x,&y);

        w[x][y][0]=1;

        dis[x][y]=1;

    }

    for(int l=1;l<=50;l++)

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

    for(int k=1;k<=n;k++)

    if(i!=j&&j!=k&&i!=j)

    if(w[i][k][l-1]&&w[k][j][l-1])

    w[i][j][l]=1,dis[i][j]=1;

    for(int i=1;i<=n;i++)

    for(int j=1;j<=n;j++)

    for(int k=1;k<=n;k++)

    if(i!=j&&j!=k&&i!=j)

      dis[i][j]=min(1ll*dis[i][j],1ll*dis[i][k]+dis[k][j]);

    cout<<dis[1][n]<<endl;

    return 0;

}

巴特西

P1613 跑路 (最短路,倍增)

题目链接

Solution

Code

最新文章

热门文章