SDUT2139图结构练习——BFS——从起始点到目标点的最短步数

淡淡的烟草味﹌ 2022-07-15 04:55 55阅读 0赞

\#include <bits/stdc++.h>  
using namespace std;  
\#define maxn 10086  
int num\[maxn\]; //记录到n结点的最短距离  
int Map\[maxn\]\[maxn\]; //记录结点的连通性  
int vis\[maxn\]; //记录是否已遍历过改结点  
int Now\[maxn\]; //储存已遍历的结点  
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; //初始化为0  
while(ss>ee)  
\{  
int now = Now\[e++\]; //得到队列的首元素  
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开始查找；  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，55人围观）

还没有评论，来说两句吧...

相关阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

think: 1广度优先搜索体现了一种队列思想，而深度优先搜索则体现了一种递归思想，广度优先搜索与深度优先搜索可以说互相是一种协调互补共同结局问题的方法或思想，经过最近假期

落日映苍穹つ/ 2022年09月27日 12:28/ 0 赞/ 49 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

图结构练习——BFS——从起始点到目标点的最短步数 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描

曾经终败给现在/ 2022年08月10日 06:11/ 0 赞/ 35 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

图结构练习——BFS——从起始点到目标点的最短步数 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Stati

清疚/ 2022年07月15日 04:55/ 0 赞/ 54 阅读

相关 SDUT2139图结构练习——BFS——从起始点到目标点的最短步数

\include <bits/stdc++.h> using namespace std; \define maxn 10086 int num\[maxn\];

淡淡的烟草味﹌/ 2022年07月15日 04:55/ 0 赞/ 56 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

Problem Description 在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。其中

谁践踏了优雅/ 2022年07月12日 11:36/ 0 赞/ 65 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

Problem Description 在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。

港控/mmm°/ 2022年07月12日 07:26/ 0 赞/ 52 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

Problem Description 在古老的魔兽传说中，有两个军团，一个叫天灾，一个叫近卫。在他们所在的地域，有n个隘口，编号为1..n，某些隘口之间是有通道连接的。

冷不防/ 2022年07月12日 07:26/ 0 赞/ 56 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

think: 1结构数组+广度优先搜索 2逆推思想 [sdut原题链接][sdut] 图结构练习——BFS——从起始点到目标点的最短步数 Time Limit:

待我称王封你为后i/ 2022年07月12日 07:12/ 0 赞/ 53 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

think: 1结构数组+广度优先搜索 2逆推思想 [sdut原题链接][sdut] 图结构练习——BFS——从起始点到目标点的最短步数 Time Limit:

本是古典何须时尚/ 2022年07月12日 07:12/ 0 赞/ 56 阅读

相关图结构练习——BFS——从起始点到目标点的最短步数

图结构练习——BFS——从起始点到目标点的最短步数 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic

川长思鸟来/ 2022年06月10日 12:51/ 0 赞/ 51 阅读