洛谷——P1613 跑路

P1613 跑路

题目大意：

小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

倍增+Floyd处理

首先不能直接跑最短路，因为跑路机的存在，可以想到倍增，每次向上跳最大可能步数，但就样例来说，1~n的树上路径是3，无法考虑到包含自环的点

设$p[i][j][k]$为$i$到$j$路径长度为$2^k$的路径是否存在，倍增就好了，然后Floyd求最短路。

#include<bits/stdc++.h>

#define N 101010

using namespace std;

int d[][],n,m;

bool p[][][];

int main()

{

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

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

    for(int u,v,i=;i<=m;i++){

        scanf("%d%d",&u,&v);

        d[u][v]=;

        p[u][v][]=true;

    }

    for(int k=;k<=;k++){

        for(int f=;f<=n;f++)

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

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

                    if(p[i][f][k-]&&p[f][j][k-])

                        p[i][j][k]=true,d[i][j]=;

                }

            }

    }

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

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

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

                d[i][j]=min(d[i][k]+d[k][j],d[i][j]);

            }

        }

    }

    printf("%d\n",d[][n]);

    return ;

}