P1613 跑路

题目描述

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

输入输出格式

输入格式:

第一行两个整数\(n\),\(m\),表示点的个数和边的个数。

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

输出格式:

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

说明

\(50\)%的数据满足最优解路径长度\(<=1000\);

\(100\)%的数据满足\(n<=50\),\(m<=10000\),最优解路径长度\(<=\) \(max\) \(long\) \(int\)。


首先,要确保自己的语文水平苟的住,这个鬼机器,每秒跑\(2^kkm\)的话是要跑刚好那么长的,不能多也不能少。

那么岂不是代表,只有长为\(2^kkm\)的链才算是有效边吗?

我们把所有有效边连上,跑最短路不就行了嘛。

如何求有效边?

\(2^k?\)有没有想到什么?

\(2^k=2^{k-1}+2^{k-1}?\)

对,就是倍增啊!

令\(g[u][v][j]\)代表点\(u\)到点\(v\)存在或不存在长度为\(2^j\)的边。

当\(g[u][k][j-1]\)和\(g[k][v][j-1]\)同时存在时,

\(g[u][v][j]\)存在。(\(k\)是枚举的一维)


#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=52;
int g[N][N][70],n,m;
//g[i][j][k]表示i点到j点存在边权为2^k的路
int g0[N][N];
int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    return x;
}
queue <int > q;
int used[N],dis[N];
void spfa()
{
    memset(used,0,sizeof(used));
    used[1]=1;
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        used[u]=0;
        for(int v=1;v<=n;v++)
            if(g0[u][v]&&dis[v]>dis[u]+g0[u][v])
            {
                dis[v]=dis[u]+g0[u][v];
                if(!used[v])
                {
                    used[v]=1;
                    q.push(v);
                }
            }
    }
}

int main()
{
    memset(g,0,sizeof(g));
    memset(g0,0,sizeof(g0));
    n=read(),m=read();
    int u,v;
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read();
        g[u][v][0]=1;
        //f[u][v][0]=v;
    }
    for(int j=1;j<=64;j++)
        for(int k=1;k<=n;k++)
            for(u=1;u<=n;u++)
                for(v=1;v<=n;v++)
                    if(g[u][k][j-1]&&g[k][v][j-1])
                        g[u][v][j]=1;
    for(u=1;u<=n;u++)
        for(v=1;v<=n;v++)
            for(int j=0;j<=64;j++)
                if(g[u][v][j])
                {
                    g0[u][v]=1;
                    break;
                }
    spfa();
    printf("%d\n",dis[n]);
    return 0;
}

2018.5.2

最新文章

  1. NULL指针、零指针、野指针
  2. 如何设计PHP业务模块(函数/方法)返回结果的结构?
  3. web api post注意事项
  4. Asp.net Vnext Routing
  5. Windows7配置GPU和Theano编程环境
  6. lex&amp;yacc5--YYSTYPE
  7. Django开发网站(二)
  8. Apache Kafka: Next Generation Distributed Messaging System---reference
  9. 研究不定数量参数的函数并实现一个printf函数
  10. 关于HttpServlet和Servlet以及doPost和doGet关系
  11. PHP数组foreach后使用current取值的问题
  12. Windows下配置Mysql
  13. 中英文url解码vc++源程序
  14. 在IntelliJ IDEA里创建简单的基于Maven的SpringMVC项目
  15. Express使用进阶:cookie-parser中间件实现深入剖析
  16. LAMP 搭建
  17. python2.7入门---运算符
  18. 下载Android源代码编译错误总结
  19. MinerStoreThread.java 存储线程
  20. CTFcracktools——非常实用的CTF解密工具

热门文章

  1. 新版 itextsharp pdf code
  2. .net core 基本概念
  3. vlc播放yuv文件
  4. Mycat配置文件rule.xml
  5. TP第一天路由解析
  6. 笔记3:关于VBS整人代码的浅谈
  7. 调试Android USB遇到的令人费解的问题
  8. gitlab ActionView::Template::Error (undefined method `[]&#39; for nil:NilClass): 500错误
  9. poj2484--A Funny♂Game
  10. Ubuntu安装JDK(tar.gz)
  11. Basic Calculator I &amp;&amp; II &amp;&amp; III
  12. 06-HTML-表格标签
  13. 剑指Offer-- 二叉搜索树的后序遍历序列判断
  14. Guava学习笔记(一):Maven
  15. 【其他】【服务器】【4】删除Windows系统中不想要的服务
  16. transaction注解分析
  17. 使用 IDEA 开发工具(版本为 IntelliJ IDEA 14.1.4)打可执行jar包的操作步骤
  18. ccf窗口
  19. Day14 作业
  20. 转载【小程序】: 微信小程序开发---应用与页面的生命周期