题面
传送门:洛咕
Solution
挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到2的n次方，那么这两个点可以用1的时间相互到达。 也就是说，我们把距离能为2的n次方的点对用边权为1的边连上，再做一次最短路径，就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。 考虑使用DP。 我们设$f[i][j][k]$ 表示 $i$到$j$是否能以$2$的$k$次方的距离相互到达。 转移的时候得运用倍增的思想：若两个点能以两端$2$的$k-1$次方的距离相互到达，那么两个点就能以2的k次方的距离相互到。 接下来我们就可以运用类似Floyd的办法来处理这个DP，我们可以在最外层枚举这个k，里面三层和Floyd的意义一模一样，就是枚举中转点与起始点。 初始化就是题目中直接相连的两个点，它们的$f[a][b][0]=1$ （它们距离为1,是2的0次方） 时间复杂度： $O(n^3*64)$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=50+10;
const int K=65+10;
int f[N][N][K],dis[N][N],n,m;
int main()
{
n=read(),m=read();
memset(dis,0x3f,sizeof dis);
for(int i=1;i<=m;i++)
{
int s=read(),t=read();
f[s][t][0]=1;
dis[s][t]=1;
}
for(int o=1;o<=64;o++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(f[j][i][o-1]==true and f[i][k][o-1]==true)
{
f[j][k][o]=true;
dis[j][k]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
printf("%d",dis[1][n]);
return 0;
}
|
