解题思路:
我们有一个动态规划的思路,利用数组记录到达i的最短次数,但这个不是无环图,不适宜使用动态规划,我们利用图建模,求最短路径,可以使用迪杰斯特拉算法求解最短路径,但对于这道题,bfs显然更加容易。
注意事项:
有向图,因为一个点到另一个点不是互相可达的,比如我们仅仅可以设想从0时间到达1时间,而不能设想1到0时间,这是不合法的。
参考代码:
#include<bits/stdc++.h> using namespace std; #define maxx 200000 int n,k,ans; int d[maxx]; vector<int> G[maxx]; void bfs() { for(int i=0;i<n;++i) d[i]=INF; queue<int> Q; Q.push(0); d[0]=0; while(!Q.empty()) { int a=Q.front(); Q.pop(); for(int j=0;j<G[a].size();++j) { if(d[G[a][j]]==INF) { d[G[a][j]]=d[a]+1; Q.push(G[a][j]); } } } } int main() { cin>>n>>k; for(int i=0;i<n;++i) { G[i].push_back((i+1)%n); G[i].push_back((i+k)%n); } bfs(); for(int i=0;i<n;++i) ans=max(ans,d[i]); cout<<ans; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:946 |
求圆的面积 (C语言代码)浏览:1272 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:607 |
A+B for Input-Output Practice (II) (C语言代码)浏览:1002 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:858 |
淘淘的名单 (C语言代码)浏览:1104 |
简单的for循环浏览:1412 |
剪刀石头布 (C语言代码)浏览:1755 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:642 |
关于C语言变量位置的问题浏览:273 |