【题解】跑路
【题解】跑路
MikeC
发布于 2022-09-21 11:44:29
发布于 2022-09-21 11:44:29
代码可运行
运行总次数：0
代码可运行
题目描述
小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说明/提示
n\le 50，m\le10000，最优解路径长度\le maxlongint。
分析
数据范围奇小，故可以考虑效率较低的最短路算法。
再分析题意，发现可以将长度为 2^k 的路看作长度为 1。因此可以利用倍增，对长度为 2^k(1 \le k \le 64) 的边进行处理，使其长度为 1。
此时我们便可以通过最短路算法得到答案，注意初始化。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int d[51][51];
int f[51][51][65];
int u,v;
signed main(){
scanf("%d%d",&n,&m);
memset(d,0x3f,sizeof(d));
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
f[u][v][0]=d[u][v]=1;
}
for(int p=1;p<=64;p++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(f[i][k][p-1]&&f[k][j][p-1]){
f[i][j][p]=d[i][j]=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]);
}
}
}
printf("%d",d[1][n]);
return 0;
}最后修改：2021 年 07 月 20 日 03 : 11 PM
© 允许规范转载
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021 年 07 月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
