P1613 跑路

跑路：先构造一次操作，再求最短路

问题

P1613 跑路 - 洛谷
给定一张边长均为 $1$ 的有向图。每秒可以沿图走过恰好 $2^k$ 条边，其中 $k$ 是任意自然数，求从 $1$ 到 $n$ 的最少秒数。

数据规模：$2\le n\le50$，最优路线总长度不超过 $2^{31}-1$。

原图中的一条边不只对应一秒：只要存在一条长度恰好为 $2^k$ 的路径，就可以在一秒内从路径起点到达终点。

所以我们没法直接在原图上求最短路，我们可以先根据题目的含义先求出所有长度为 $2^{k}$
长的路径，然后建一张新图，然后跑一遍最短路。

定义 $f_{t,u,v}=1$ 表示存在一条从 $u$ 到 $v$、长度恰好为 $2^t$ 的路径。原图中的每条边构成 $t=0$ 的基础状态。

一条长度为 $2^t$ 的路径可以在中间位置拆成两条长度为 $2^{t-1}$ 的路径，因此

$$f_{t,u,v}=\bigvee_k\left(f_{t-1,u,k} \& f_{t-1,k,v}\right).$$

这一步类似 ST 表的倍增合成。

于是只要某个 $f_{t,u,v}=1$，就在压缩后的图中加入一条 $u\to v$、边权为 $1$ 的边。压缩图上的最短路与原问题的最少秒数完全等价，由于 $n\le50$，直接使用 Floyd 求所有点对最短路即可。

状态只需建立到 $t=30$。预处理倍增可达关系的复杂度为 $O(31n^3)$，Floyd 为 $O(n^3)$，空间复杂度为 $O(31n^2)$。

▶

P1613

bool f[maxn][maxn][maxn]; // f[t][u][v] : 存在一条长度为 2^t 的路径，从 u 到 v
ll dis[maxn][maxn];

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        f[0][u][v] = 1;
    }

    for( int t = 1; t <= 30; ++ t ) {
        for( int k = 1; k <= n; ++ k ) {
            for( int u = 1; u <= n; ++ u ) {
                for( int v = 1; v <= n; ++ v ) {
                    f[t][u][v] |= f[t-1][u][k] && f[t-1][k][v];
                }
            }
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            if( i == j ) dis[i][j] = 0;
            else dis[i][j] = inf;
        }
    }

    for( int t = 0; t <= 30; ++ t ) {
        for( int u = 1; u <= n; ++ u ) {
            for( int v = 1; v <= n; ++ v ) {
                if( f[t][u][v] ) dis[u][v] = min( dis[u][v], 1ll );
            }
        }
    }

    for( int k = 1; k <= n; ++ k ) {
        for( int u = 1; u <= n; ++ u ) {
            for( int v = 1; v <= n; ++ v ) {
                dis[u][v] = min( dis[u][v], dis[u][k] + dis[k][v] );
            }
        }
    }

    cout << dis[1][n] << '\n';
}

记录

• 新增：当一次操作跨越的不是原图的一条边时，应先重新定义边；倍增 DP 负责构造可用操作，最短路负责组合这些操作。

• 分类：C