首页 > 其他 > 详细

【洛谷P1613】跑路

时间:2019-05-03 15:10:17      阅读:117      评论:0      收藏:0      [点我收藏+]

这道题说每一步可以走2k个距离,那么这道题就直接和倍增建立了联系。

由于n的范围很小,我们可以用Floyd处理边的关系,定义vis[i][j][k]表示ij之间是否存在2k的路径,dis[i][j]表示ij之间的最短距离是多少。

我们可以先进行一次Floyd处理vis,枚举ij以及中间点k,若vis[i][k][l-1]==1且vis[k][j][l-1]==1那么有vis[i][j][l]=1且dis[i][j]=1.

我们在进行一次Floyd,维护dis即可,答案就是dis[1][n].

技术分享图片
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 int n,m,dis[60][60],vis[60][60][70];
 8 int main() {
 9     cin>>n>>m;
10     memset(dis,0x3f,sizeof(dis));
11     memset(vis,0,sizeof(vis));
12     // cout<<dis[1][n];
13     for(int i=1;i<=m;i++) {
14         int x,y;
15         cin>>x>>y;
16         vis[x][y][0]=1;
17         dis[x][y]=1;
18     }
19     for(int l=1;l<=64;l++)
20         for(int i=1;i<=n;i++)
21             for(int j=1;j<=n;j++)
22                 for(int k=1;k<=n;k++)
23                     if(vis[j][i][l-1]==1&&vis[i][k][l-1]==1) {
24                         vis[j][k][l]=1;
25                         dis[j][k]=1;
26                     }
27     for(int k=1;k<=n;k++)
28         for(int i=1;i<=n;i++)
29             for(int j=1;j<=n;j++)
30                 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
31     cout<<dis[1][n]<<endl;
32     return 0;
33 }
AC Code

 

【洛谷P1613】跑路

原文:https://www.cnblogs.com/shl-blog/p/10805165.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!