[luogu p1613] 跑路

(mathtt{Link})

传送门

(mathtt{Summarization})

给定一个有向图 (G)，进行一次操作可以走 (2 ^ k) 条边，求 (1 ightarrow n) 的最小操作数。

(mathtt{Solution})

看到一次操作 (2 ^ k) 自然想到倍增。

再看到如此弱的数据范围，(n le 50)，一般五层循环嵌套都没问题。

那就可以放心采用这样一种做法了：

定义一个数组 dir，定义 dir[i][j][k] 为 从 i -> j 是否有一条长度为 (2 ^ k) 的路径。

便可以想到一种暴力倍增的方案：每次枚举 (k)，并枚举 (u, v) 两个点，再枚举一个 (i) 作为中转点。

有：

[dir_{u,i,k-1} = ext{true}, dir_{i, v, k - 1} = ext{true} ightarrow dir_{u, v, k} = ext{true} ]

至于初始条件，显然：

[u ightarrow v in G ightarrow dir_{u, v, 0} = ext{true} ]

那么，(dir) 和 (dis) 之间的关系怎么求呢？

对于两个顶点 (u, v)，若存在一个 (k) 使得 (dir_{u, v, k} = ext{true})，那么 (dis_{u, v} = 1)。

最后根据这些 (dis) 用 floyd 求最短路即可。

(mathtt{Time} ext{ } mathtt{Complexity})

核心倍增复杂度：(mathcal{O}(log dis imes n ^ 3))

floyd复杂度：(mathcal{O}(n^3))

所以整体复杂度是 (mathcal{O}(log dis imes n ^ 3))

(mathtt{Code})

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2020-11-04 13:55:04 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2020-11-04 14:09:23
 */
#include <iostream>
#include <cstdio>
#include <cstring>

const int maxn = 55;
const int maxlogdis = 65;
inline int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline int min(int a, int b) {
    return a < b ? a : b;
}

int dis[maxn][maxn];
bool dir[maxn][maxn][maxlogdis];

int main() {
    std :: memset(dir, 0, sizeof(dir));
    std :: memset(dis, maxn, sizeof(dis));
    
    int n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        dis[u][v] = 1;
        dir[u][v][0] = true;
    }

    for (int k = 1; k < maxlogdis; ++k)
        for (int u = 1; u <= n; ++u)
            for (int i = 1; i <= n; ++i)
                for (int v = 1; v <= n; ++v)
                    if (dir[u][i][k - 1] && dir[i][v][k - 1]) {
                        dir[u][v][k] = true;
                        dis[u][v] = 1;
                    }
    
    for (int i = 1; i <= n; ++i)
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v)
                dis[u][v] = min(dis[u][v], dis[u][i] + dis[i][v]);
    
    std :: printf("%d
", dis[1][n]);
    return 0;
}

(mathtt{More})

看到这种弱数据范围一定要放心，别想太复杂。