输入
7 12 7 6 7 5 7 4 7 3 5 4 4 2 3 7 3 4 3 1 2 6 2 1 1 4
输出
2
我们要找从n到1是否有路可循，并且求最短的路径。以上图为例子，从7开始进行查找。与7节点有关，且没有被遍历过的节点有
6,5,4,3这四个节点，标记这四个节点vis[i]=1;，并记下从7到它们的最短距离num[i]=1;
下一步，查找6节点，没有条件满足的节点；
下一步，查找5节点，没有条件满足的节点；
下一步，查找4节点，与4有关且未被遍历过的节点有2这一个节点；标记节点2，num[2]=2;
下一步，查找3节点，与3有关且未被遍历过的节点有1这一个节点；标记节点1，num[1]=2;
下一步，查找2节点，没有条件满足的节点；
下一步，查找1节点，没有条件满足的节点；
查找结束；
个人觉得BFS查找的过程类似于二叉树的层序遍历；
#include <bits/stdc++.h> using namespace std; int num[1001];//记录到n节点的最短距离 int Map[1001][1001];//记录节点的连通性 int vis[1001];//记录是否已遍历过该节点 int Now[1001];//存储已遍历的节点； int n,m; int BFS(int k) { memset(vis,0,sizeof(vis)); memset(Now,0,sizeof(Now)); memset(num,1061109567,sizeof(num)); int ss=0,ee=0; Now[ss++]=k; vis[k]=1; num[k]=0; while(ss>ee) { int now=Now[ee++]; for(int i=n;i>=1;i--) { if(Map[now][i]==1&&vis[i]==0)//当前节点与i节点连通&&没有遍历过 { Now[ss++]=i;//将i节点存入 vis[i]=1;//标记已遍历过 num[i]=num[i]<num[now]?num[i]:num[now]+1;//若i节点此前到n节点的距离<当前节点到n节点的距离，num[i]不变； } //否则，i节点到n节点的距离 = num[now]+1； } } if(num[1]==1061109567) printf("NO\n"); else printf("%d\n",num[1]); } int main() { int u,v; while(~scanf("%d %d",&n,&m)) { memset(Map,0,sizeof(Map)); for(int i=0;i<m;i++) { scanf("%d %d",&u,&v); Map[u][v]=1; } BFS(n);//从n开始查找； } }
