蓝桥杯2018年第九届真题-调手表(最短路径)

解题思路:
我们有一个动态规划的思路，利用数组记录到达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;
}