题目描述
小 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
说明
[样例解释]
1->1->2->3->4, 总路径长度为 4 千米, 直接使用一次跑路器即可.
[数据范围]
50% 的数据满足最优解路径长度 <=1000;
100% 的数据满足 n<=50,m<=10000, 最优解路径长度 <=maxlongint.
Solution:
本题思路贼有意思.
首先按照题意每次能跳 $2^k$ 的距离, 不难想到用倍增, 关键是倍增该怎么用到本题上.
很容易想到用倍增来预处理每个点能一次跳到的点并建边, 那么问题就转化为了最短路问题了.
初始化设 $g[i][j][k]$ 表示的是 $i$ 到 $j$ 能通过跳 $2^k$ 一步到达, 读入时便能处理出所有 $k=0$ 的情况, 然后就能直接倍增预处理了, 状态转移方程为 $g[i][j][k]=g[i][t][k-1]&g[t][j][k-1]$(意味着 $i$ 到 $t$ 能跳 $2^{k-1}$ 次一步到达,$t$ 到 $j$ 能跳 $2^{k-1}$ 一步到达, 那么 $i$ 到 $t$ 能跳 $2^{k-1}+2^{k-1}=2^k$ 次一步到达), 能一步到的就连边权为 $1$.
最后只需要跑一下最短路就好了,$n\leq 50$ 且题目中边所连的点还能相同, 直接跑 $floyd$ 就可以了.
代码:
- #include<bits/stdc++.h>
- #define il inline
- #define ll long long
- #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
- #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
- using namespace std;
- int n,m,mp[55][55];
- bool vis[55],g[55][55][25];
- il int gi(){
- int a=0;char x=getchar();bool f=0;
- while((x<'0'||x>'9')&&x!='-')x=getchar();
- if(x=='-')x=getchar(),f=1;
- while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
- return f?-a:a;
- }
- int main(){
- n=gi(),m=gi();
- int u,v;
- memset(mp,0x3f,sizeof(mp));
- For(i,1,m) u=gi(),v=gi(),g[u][v][0]=1,mp[u][v]=1;
- For(k,1,24) For(i,1,n) For(t,1,n) For(j,1,n)
- if(g[i][t][k-1]&&g[t][j][k-1]) g[i][j][k]=1,mp[i][j]=1;
- For(k,1,n) For(i,1,n) For(j,1,n) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
- cout<<mp[1][n];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2690693.html