【题解】Luogu P1613 跑路 倍增+最短路

概述题里都说了$2^k$，明显倍增 因为跑路器的存在，不能直接跑最短路的原因： 如图，如果直接最短路从1号点到5号点的距离为3，需要3秒 而实际上走$1->5$这条边，因为$8=2^3$，只需1秒     $n≤50$直接无脑floyed随便跑 code 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{

题里都说了^k$，明显倍增

因为跑路器的存在，不能直接跑最短路的原因：

如图，如果直接最短路从1号点到5号点的距离为3，需要3秒

而实际上走->5$这条边，因为=2^3$，只需1秒

 

 

$n≤50$直接无脑floyed随便跑

code

 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int maxn=1e6+10; 6 inline int read(){ 7     int x=0,f=1; 8     char c=getchar(); 9     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}10     while(c>=‘0‘&&c<=‘9‘){x=(x*10)+c-‘0‘;c=getchar();}11     return x*f;12 }13 int n,m,dis[60][60];//dis[i][j]从i到j所需的时间14 bool e[60][60][35];//e[i][j][k]是否存在一条从i到j距离是2^k的路径15 int main(){16     memset(dis,0x3f3f3f3f,sizeof(dis));17     n=read();m=read();18     for(int i=1;i<=m;i++){19         int u,v;u=read();v=read();20         e[u][v][0]=1;21         dis[u][v]=1;22     }23     for(int t=1;t<=35;t++)24         for(int i=1;i<=n;i++)25             for(int j=1;j<=n;j++)26                 for(int k=1;k<=n;k++){27                     if(e[i][j][t-1]&&e[j][k][t-1]){28                         e[i][k][t]=1;29                         dis[i][k]=1;30                     }31                 }32     for(int k=1;k<=n;k++)33         for(int i=1;i<=n;i++)34             for(int j=1;j<=n;j++){35                 dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);36             }37     printf("%d",dis[1][n]);38     return 0;39 }40 }41 signed main(){42   gengyf::main();43   return 0;44 }

VIEw Code 总结

以上是内存溢出为你收集整理的【题解】Luogu P1613 跑路 倍增+最短路全部内容，希望文章能够帮你解决【题解】Luogu P1613 跑路 倍增+最短路所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。