标签: Floyd

[洛谷1613]跑路 题解

[洛谷1613]跑路 题解

题目地址:洛谷:【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;
}