M_sea

洛谷1613 跑路
题目描述小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏...
扫描右侧二维码阅读全文
05
2018/08

洛谷1613 跑路

题目描述

小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家为点1,公司为点n,每条边长度均为一千米。小A想每天能醒地尽量晚,所以让你帮他算算,他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

传送门

算法

题目中有个$2^k$,倍增,很稳。

设$f[i][j][k]$表示从$i$走$2^k$步能否到$j$。可以用类似Floyd的方式来更新。

在推$f$的时候,顺便将$G[i][j]$赋值为$1$。

然后一遍Floyd即可。

(数据小随便搞)

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int G[60][60];
bool f[60][60][74];

int main() {
    int n=read(),m=read();
    memset(G,0x3f,sizeof(G));
    for (re int i=1;i<=m;i++) {
        int x=read(),y=read();
        G[x][y]=1;
        f[x][y][0]=1;
    }
    
    for (re int t=1;t<=64;t++)
        for (re int k=1;k<=n;k++)
            for (re int i=1;i<=n;i++)
                for (re int j=1;j<=n;j++)
                    if (f[i][k][t-1]&&f[k][j][t-1]) {
                        f[i][j][t]=1;
                        G[i][j]=1;
                    }
    
    for (re int k=1;k<=n;k++)
        for (re int i=1;i<=n;i++)
            for (re int j=1;j<=n;j++)
                if (G[i][k]+G[k][j]<G[i][j])
                    G[i][j]=G[i][k]+G[k][j];
    
    printf("%d\n",G[1][n]);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 01 PM

发表评论