题目内容

有向图,边权为 1,可以在 1 秒内跳 2^k km,求从 1 到 n 的最短时间

解题思路

倍增优化 dp。

数据范围很小,可以先预处理出 xy 之间是否存在长度为 2^k 的路径,然后直接更新两点间路径长度,跑一遍 Floyd 即可。

预处理的具体方法是枚举中转点 z,如果 xz 之间和 zy 之间都有长度为 2^{k-1} 的路径的话,xy 之间就必然有长度为 2^k 的路径

#include <cstdio>
#include <cctype>
#include <cstring>

typedef long long ll;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline ll min(ll a,ll b)
{
    return a<b?a:b;
}

const int maxn=53;
ll dis[maxn][maxn],n,m;
bool G[maxn][maxn][64];

int main()
{
    memset(dis,0x3f,sizeof dis);
    n=read(),m=read();
    while(m--)
    {
        int x=read(),y=read();
        G[x][y][0]=true;
        dis[x][y]=1;
    }
    for(int k=1;k<=64;k++)
        for(int x=1;x<=n;x++)
            for(int y=1;y<=n;y++)
                for(int z=1;z<=n;z++)
                    if(G[x][z][k-1] && G[z][y][k-1])
                        G[x][y][k]=true,dis[x][y]=1;//预处理两点之间是否有 2^k 路径
    for(int x=1;x<=n;x++)
        for(int y=1;y<=n;y++)
            for(int z=1;z<=n;z++)
                dis[x][y]=min(dis[x][y],dis[x][z]+dis[z][y]);
    printf("%lld\n",dis[1][n]);
    return 0;
}
最后修改日期:2020年9月15日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。