P1613跑路

一道倍增好题,题目问的很有意思,看起来似乎是个单源最短路,但是每次前进的路程都必须要是2的倍数,所以最短路算法求出来的不是一定对,那看到2自然就会想到倍增的思想,所以维护一个$f[i][j][k]$表示i到j是否存在2的k次方的路径,之后顺便维护dis往上倍增,因为这样复杂度就高达了$O(n^4)$所以再求最短路时就可以直接用复杂度高的floyd而不必用spfa之类的,反正n<50,数据范围不大

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
int n,m,dis[55][55],f[55][55][65];
int main()
{
    memset(dis,10,sizeof(dis));
    memset(f,0,sizeof(f));
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        dis[x][y]=1;
        f[x][y][0]=1;
    }
    for(int l=1;l<=60;l++)
        for(int i=1;i<=n;i++)
            for(int k=1;k<=n;k++)
                for(int j=1;j<=n;j++)
                if(f[i][k][l-1]&&f[k][j][l-1])
                {
                    f[i][j][l]=1;
                    dis[i][j]=1;
                }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    cout<<dis[1][n]<<endl;
    return 0;
}