关键词:
题目描述
小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的边。
输出格式:
一行一个数字,表示到公司的最少秒数。
输入输出样例
4 4 1 1 1 2 2 3 3 4
1
说明
【样例解释】
1->1->2->3->4,总路径长度为4千米,直接使用一次跑路器即可。
【数据范围】
50%的数据满足最优解路径长度<=1000;
100%的数据满足n<=50,m<=10000,最优解路径长度<=maxlongint。
看到2 ^ k 就想到了倍增, 用一个数组to[x][j][y], 表示x + 2 ^ j能不能走到y, 能就标记1, 最后Floyed
中间一个倍增数组, i + 2^(o - 1) = j, j + 2^(o - 1) = k i -> k i + 2^o = k;
#include <iostream> #include <cstdio> #define F(i, l, r) for(int i = l; i <= r; ++i) using namespace std; const int MAX = 51; const int POW = 32; const int INF = 1000000; int N, M; int dis[MAX][MAX]; bool to[MAX][POW + 1][MAX]; int read() { int x = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘) { if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - ‘0‘; ch = getchar(); } return x * f; } void Input() { N = read(); M = read(); F(i, 1, N) F(j, 1, N) dis[i][j] = INF; F(i, 1, M) { int x, y; x = read(); y = read(); dis[x][y] = 1; to[x][0][y] = 1; } return; } void pre() { for(int o = 1; o <= POW; ++o) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) if(to[i][o - 1][j]) for(int k = 1; k <= N; k++) if(to[j][o - 1][k]) to[i][o][k] = 1, dis[i][k] = 1; return; } void Floyed() { F(k, 1, N) F(i, 1, N) F(j, 1, N) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); return; } int main() { Input(); pre(); Floyed(); printf("%d", dis[1][N]); return 0; }
洛谷1613跑路解题记录
题目描述小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米... 查看详情
洛谷p1613解题报告
P1613跑路题目描述小\(A\)的工作不仅繁琐,更有苛刻的规定,要求小\(A\)每天早上在\(6:00\)之前到达公司,否则这个月工资清零。可是小\(A\)偏偏又有赖床的坏毛病。于是为了保住自己的工资,小\(A\)买了一个十分牛B的空间跑路器... 查看详情
bzoj4892
...O(nlogn+n),然后t掉了,交了发别人代码,bzoj怎么那么慢,洛谷跑的飞快。调了很长时间发现sa板子写错了,明明是粘过来的。。。后缀自动机就是在自动机上匹配,如果不匹配可以随便走,每次匹配完 查看详情
删库跑路技巧删库跑路命令(代码片段)
1.Linux操作系统上的删库跑路#删除根目录下所有文件,杀伤力极大,请谨慎使用#此命令一出,Linux根目录下很多文件,可以能彻底从这个星球上彻底消失了rm-rf/*#指定路径删除,菜刀可以用来做菜亦可以用来s人rm-rf/home/fileName2.sql上... 查看详情
[bzoj1058][zjoi2007]报表统计
...离散化+线段树. 这个方式的常数太大,会T。我在洛谷跑最后两个点TLE了,在BZOJRE了。 具体说一下怎么做吧。首先把所有数离散化,把出现过的绝对值离散化。这样我们就能得到约n+m个数和n+m个绝对值。然后,维... 查看详情
删库跑路计划图鉴
luogup1613跑路
P1613跑路2017-09-17题目描述小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒... 查看详情
p1613跑路
P1613跑路题目描述小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以... 查看详情
p1613跑路
P1613跑路题目描述小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以... 查看详情
luogup1613跑路(代码片段)
【Luogu】P1613跑路一、题目题目描述小A的工作不仅繁琐,更有苛刻的规定,要求小A每天早上在6:00之前到达公司,否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路... 查看详情
p1613跑路
...。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家... 查看详情
你问我为啥要跑路啊?
...;,硬核文章第一时间送达!【0】你说我为什么要跑路啊【1】从删库到跑路【2】删库之前最后一项准备当然,以下任何有一个原因也可能成为我跑路的原因:【3】加班加成狗【4】想要一头茂密的秀发【5】别人都... 查看详情
[luogu]跑路
https://www.luogu.org/problemnew/show/P1613Floyd判断是否一步到达将一步到达的连变跑Floyd#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintN=70;const 查看详情
程序员的趣事-删库,跑路?
...员的圈子里一直流传着这样的一个笑话,那就是删库跑路一不小心,删库,跑路,干的不爽,删库,跑路意思就是把数据中心数据全删了,这其实是个真实的事件,话说几年前,一个互联网大厂... 查看详情
p1613跑路(代码片段)
...。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家... 查看详情
跑路(倍增+最短路)(代码片段)
...。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家... 查看详情
p1613跑路(代码片段)
...。于是为了保住自己的工资,小A买了一个十分牛B的空间跑路器,每秒钟可以跑2^k千米(k是任意自然数)。当然,这个机器是用longint存的,所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图,小A家... 查看详情
luogu_1613跑路
#include<cstdio>#include<iostream>#include<queue>#include<cctype>#include<vector>#include<cstring>usingnamespacestd;intn,m,d[70][70];boolG[70][70][70];intread(){cha 查看详情