P1613 跑路

P1613 跑路 (倍增优化DP）

对于不擅长倍增的同学….这是个很好的入门题

题目描述

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

输入格式

第一行两个整数n，m，表示点的个数和边的个数。

接下来m行每行两个数字u，v，表示一条u到v的边。

输出格式

一行一个数字，表示到公司的最少秒数。

输入 #1

4 4
1 1
1 2
2 3
3 4

输出 #1

1

【数据范围】

50%的数据满足最优解路径长度<=1000；

100%的数据满足n<=50，m<=10000，最优解路径长度<=maxlongint。

==================================================================

看起来这是个恶心的题

题目讲

小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米

这不就是个倍增吗？一个最短路加倍增！

然后就是推到状态看题解

其实题目比较唬人，加上不经常接触倍增，可能看到就不想去写了

但其实
确实唬人

题目的意思其实就是，

如果两点的距离是2的次方，那么可将其距离视为1
由观察得 ： n <= 50 , k <= 32

Floyd就完事了，

用个倍增处理出两个距离为2的正整数次幂的点，让他们的距离变成1，

原理就是如果 x 到 k 的距离是 2 ^ ( t – 1 ) , k 到 y 的距离也是 2 ^ ( t – 1 )，那么 x 到 y 的距离就是2^t

然后搞Floyd就行了

最后再有一个紧张刺激的调试环节就行了，还好我写了五分钟一次过

code

#include 
#include 

using namespace std;

const int N = 60;

int n,m;
bool g[N][N][40];//两个点是否距离为1
int d[N][N];//用来跑最短路

int main()
{
    memset(d,0x3f,sizeof d);
    cin >> n >> m;
    for(int i = 1;i <= m;i ++)
    {
        int x,y;
        cin >> x >> y;
        g[x][y][0] = 1;
        d[x][y] = 1;
    }
    //上楼梯就完事了
    for(int t = 1;t <= 33;t ++)
        for(int x = 1;x <= n;x ++)
            for(int y = 1;y <= n;y ++)
                for(int k = 1;k <= n;k ++)
                    if(g[x][k][t - 1] && g[k][y][t - 1])
                        g[x][y][t] = 1,d[x][y] = 1;
    for(int k = 1;k <= n;k ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
    cout << d[1][n];
    return 0;
}