Luogu_P1613跑路

题目大意

题目中要求的是从1号点到n号点所需要的最短时间, 一秒可以走 \(2^k\) 个距离

给定的有向图的边边权都是1.

问题分析

由于一秒可以走 \(2^k\) 个距离,因此题目转化为寻找两个点之间的距离为\(2^k\)的点对,并把边权(代表时间)赋值为1, 由于给定边权(指路径长度)都是1,

因此我们可以采用dp的思想,长度为\(2^K\)的路径可以由两个\(2^{k-1}\)的路径组合而成,至于为什么不考虑其他的组合方式,原因是初始边权都为1,如果能由其他组合方式组合而成,那么一定可以由两个\(2^{k-1}\)的路径组合而成.所以我们只需要先求出所有距离为\(2^k\)的点对,并把他们两个的时间边权赋值为1然后求最短路即可.

AC_CODE

#include <cstring>

#include <iostream>

const int N = 55;

int n, m, dist[N][N], dis[N];

bool g[N][N][64], st[N];

int main() {

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cin >> n >> m;

    memset(dist, 0x3f, sizeof dist);

    memset(dis, 0x3f, sizeof dis);

    while(m --) {

        int a, b;

        std::cin >> a >> b;

        dist[a][b] = 1;

        g[a][b][0] = true;

    }

    for(int k = 1; k <= 64; k ++ )

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

            for(int t = 1; t <= n; t ++ )

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

                    if(g[i][t][k - 1] && g[t][j][k - 1]) {

                        g[i][j][k] = true;

                        dist[i][j] = 1;

                    }

                }

    dis[1] = 0;

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

        int t = 0;

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

            if(!st[j] && (!t || dis[j] < dis[t]))

                t = j;

        st[t] = true;

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

            dis[j] = std::min(dis[j], dis[t] + dist[t][j]);

    }

    std::cout << dis[n];

    return 0;

}

巴特西

Luogu_P1613跑路

题目大意

问题分析

AC_CODE

最新文章

热门文章