题目传送门
[题目大意]
[思路分析]
我们设 $g[i][j][k]$ 表示从 $i$ 走 $2^k$ 步能否到达 $j$,$d[i][j]$ 表示 $i$ 到 $j$ 最少要走多少秒.
用倍增预处理出 $g$, 然后就可以 $Floyd$ 跑最短路啦! QwQ
[代码实现]
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- #include<queue>
- #define g() getchar()
- #define rg register
- #define go(i,a,b) for(rg int i=a;i<=b;i++)
- #define back(i,a,b) for(rg int i=a;i>=b;i--)
- #define db double
- #define ll long long
- #define il inline
- #define pf printf
- #define mem(a,b) memset(a,b,sizeof(a))
- using namespace std;
- int fr(){
- int w=0,q=1;
- char ch=g();
- while(ch<'0'||ch>'9'){
- if(ch=='-') q=-1;
- ch=g();
- }
- while(ch>='0'&&ch<='9') w=(w<<1)+(w<<3)+ch-'0',ch=g();
- return w*q;
- }
- const int N=52;
- int n,m,d[N][N];
- bool f[N][N][65];
- int main(){
- //freopen("","r",stdin);
- //freopen("","w",stdout);
- n=fr();m=fr();mem(d,0x3f);
- go(i,1,m){
- rg int x=fr(),y=fr();
- d[x][y]=1;f[x][y][0]=1;
- }
- go(k,1,64) go(i,1,n) go(t,1,n) go(j,1,n)// 注意循环嵌套的顺序
- if(f[i][t][k-1]&&f[t][j][k-1]) f[i][j][k]=1,d[i][j]=1;
- go(k,1,n) go(i,1,n) go(j,1,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
- pf("%d\n",d[1][n]);
- return 0;
- }
代码戳这里
来源: http://www.bubuko.com/infodetail-3221987.html