这篇文章上次修改于 386 天前,可能其部分内容已经发生变化,如有疑问可询问作者。
本文共 1150 个字,阅读时长 ≈ 3 分钟
P1613 跑路
题意
一个有向图,每条边长度均为一千米,每秒可以走 $2^k$ 千米(k为任意自然数)且不能中途停下,也就是要走就走恰好 $2^k$ 千米,问几秒钟能恰好从1到n。
思路
看到 $2^k$,可以往倍增的方向去想,考虑找出所有 $2^k$ 次方长度的路径,并将这个路径的起点和终点连一条边权为1的边,跑最短路即可。找路径时枚举中间点,如果起点到中间点以及中间点到终点均存在长度 $2^{k-1}$ 的路径,那么起点到终点自然存在长度为 $2^k$ 的路径。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<climits>
#ifdef ONLINE_JUDGE
#define debug(x)
#else
#define debug(x) cout<<' '<<#x<<'='<<x<<endl
#endif
using namespace std;
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
const int N=60,inf=INT_MAX>>1;
int n,m;
int a[N][N];
bool f[N][N][65];
int main()
{
n=read();
m=read();
//初始化以及读入边
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) a[i][j]=inf;
for(int i=0;i<m;++i){
int u=read(),v=read();
a[u][v]=1;
//u到v有长度为1的路径
f[u][v][0]=1;
}
//枚举k的大小以及三个点
//起点、中间点、终点
//k不用太大64就够了
for(int k=1;k<64;++k)
for(int i=1;i<=n;++i)
for(int o=1;o<=n;++o)
for(int j=1;j<=n;++j)
if(f[i][o][k-1]&&f[o][j][k-1]){
//如果两边都存在长度为2^k-1的
//路径那么就存在长度为2^k的路径
f[i][j][k]=1;
a[i][j]=1;
}
//直接跑floyd
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
printf("%d\n",a[1][n]);
return 0;
}
已有 3 条评论
看不懂纯路过~
@TeacherDu 专业不对口.jpg
@没有楼的楼长 是呢~