洛谷P1613 跑路(倍增+最短路)

题目描述

小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
好题。
首先很重要的就是:绝不是求最短路然后倍增距离求解(一开始没仔细读题...蓝题不会这么简单的QAQ)因为比如1到3的最短路可能是5,显然得用两次跑路器,但如果还有一条路长度为8,就能只使用一次跑路器了!
这就提醒我们,一定要利用好这个跑路器,只要两个点之间有一条长度为2的k次方的路径,就能一秒钟走完。因此建一个三维数组,f[i][j][k]表示i到j是否有一条长度为2的k次方的路径,是的话值为1,反之为0;同时建一个mmap数组用来一条边一条边地建立更新过的图(主要用来跑Floyd)。读入时进行初始化,f[x][y][0]=1,mmap[x][y]=1;然后首先进行一个类似Floyd的过程,因为i~k,k~j如果都存在长度为2的p-1次方的路径,那么i~j显然存在长度为2的p次方的路径,四重循环更新f数组,同时mmap[i][j]=1(直接一次跑路器就能解决)。这里要注意p这一重一定要放在最外面!因为这类似于动态规划的“阶段”。
更新完后用压缩过的图跑Floyd就好了(因为N很小)。
#include <bits/stdc++.h>
#define N 55
using namespace std;
//这个题很重要的一点就是一定不能直接求最短路然后倍增计算!!因为1到3的最短路可能是5,但还有别的长度为2的k次方的路,这样就能直接一秒到达而不是跑两秒了 
bool f[N][N][65]={0};//f[i][j][k]表示i到j是否存在一条长度为2的k次方的边 
int mmap[N][N];
int n,m;
int main()
{
    cin>>n>>m;
    int i,j,k,p;
    memset(mmap,0x3f3f3f3f,sizeof(mmap));//不能用={0x3f3f3f3f} 
    memset(f,0,sizeof(f));
    for(i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        f[x][y][0]=1;
        mmap[x][y]=1;
    }
    for(p=1;p<=64;p++)//类似动态规划 p也是阶段 得放到外面 
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                for(k=1;k<=n;k++)
                {
                    if(f[i][k][p-1]&&f[k][j][p-1])
                    {
                        f[i][j][p]=1;
                        mmap[i][j]=1;
                    }
                }
            }
        }
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                mmap[i][j]=min(mmap[i][k]+mmap[k][j],mmap[i][j]);
            }
        }
    }
    cout<<mmap[1][n];
    return 0;
}

 

                                                                                                    
上一篇:进程间通信--mmap


下一篇:GO语言基础---值传递与引用传递