---

 

如果按照常规想法,我们会考虑哪些路段走路,哪些路段搭公交,如果这样考虑就掉入陷阱之中了，因为换一组数字其情况完全不同。因为此题需要找最短时间,回顾学过的算法,BFS的特性比较复合,从N出发对坐公交和走路都进行模拟(就如同图的广度优先搜索,我们每一条方案都去试直至找到终点)。分两种情况,一种是走过了N>K，根据题意此时我们只能走路往回走,第二种是还没到,我们可以选择坐公交或者走路,每走一步时间就要加1,直至扫到位置K。

以下是代码

#include<bits/stdc++.h>

using namespace std;

struct node{//定义一个结构体

int x,t;//x表示当前位置,t表示花费时间

}p;

int main(){

int n,k;

while(cin>>n>>k){

if(n>k)//此时是第一种情况

{ cout<<n-k<<endl;break;}

int vis[2*k]={0};//此数组用于标记是否走过该结点

queue<node>q;

q.push({n,0});//起点入队

vis[n]=1;//表示此结点访问过

while(!q.empty())//开始BFS循环

{

      p = q.front();

      q.pop();

      if (p.x == k)//表明已经走到

        break;

      else if (p.x > k)

      { // 走过头了需往回走

        if (!vis[p.x - 1])

        {

          q.push({p.x - 1, p....