题目地址：洛谷：【P1613】跑路 – 洛谷

题目描述

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

输入输出格式

输入格式：
第一行两个整数n，m，表示点的个数和边的个数。
接下来m行每行两个数字u，v，表示一条u到v的边。

输出格式：
一行一个数字，表示到公司的最少秒数。

输入输出样例

输入样例#1：

4 4
1 1
1 2
2 3
3 4

输出样例#1：

1

说明

【样例解释】
1->1->2->3->4，总路径长度为4千米，直接使用一次跑路器即可。
【数据范围】
50%的数据满足最优解路径长度<=1000；
100%的数据满足n<=50，m<=10000，最优解路径长度<=maxlongint。

题解

注意到这个n范围极小，可以承受[eq]O(n^3)[/eq]算法。
跑路的长度很有趣，是[eq]2^k[/eq]，因此我们可以考虑只存一个2的指数，用gra[u][v][k]表示u到v是否存在长度为[eq]2^k[/eq]的路径。每条边会使gra[u][v][0]变为存在，k增大的时候尝试寻找两点i到j之间是否找得到中间点k使得可以拼起来两段[eq]2^{k-1}[/eq]的路径成为[eq]2^k[/eq]的路径，这里用一个类似Floyd的操作来实现即可。由于[eq]2^k[/eq]不超过longintmax，那么[eq]k \leq 64[/eq]。
对于每一对点对u, v，如果gra[u][v][k]为真，说明u到v 1秒可达，令dis[i][j]=1，再用Floyd处理最短路即可（其他最短路算法也可）。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 55;

int n, m;
bool gra[MAXN][MAXN][65];
int dis[MAXN][MAXN];

int u, v;

int main() {
    memset(dis, 0x3f, sizeof(dis));
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        u = readint(); v = readint();
        gra[u][v][0] = true;
        dis[u][v] = 1;
    }
    for(int p = 1; p <= 64; p++) {
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(gra[i][k][p - 1] && gra[k][j][p - 1]) {
                        gra[i][j][p] = true;
                        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] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    printf("%d", dis[1][n]);
    return 0;
}