一道倍增好题,题目问的很有意思,看起来似乎是个单源最短路,但是每次前进的路程都必须要是2的倍数,所以最短路算法求出来的不是一定对,那看到2自然就会想到倍增的思想,所以维护一个$f[i][j][k]$表示i到j是否存在2的k次方的路径,之后顺便维护dis往上倍增,因为这样复杂度就高达了$O(n^4)$所以再求最短路时就可以直接用复杂度高的floyd而不必用spfa之类的,反正n<50,数据范围不大
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
|
#include<bits/stdc++.h>
using namespace std;
int n,m,dis[55][55],f[55][55][65];
int main()
{
memset(dis,10,sizeof(dis));
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
dis[x][y]=1;
f[x][y][0]=1;
}
for(int l=1;l<=60;l++)
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
for(int j=1;j<=n;j++)
if(f[i][k][l-1]&&f[k][j][l-1])
{
f[i][j][l]=1;
dis[i][j]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
cout<<dis[1][n]<<endl;
return 0;
}
|