2139 数据结构实验之图论五：从起始点到目标点的最短步数（BFS）

深碍√TFBOYSˉ_ 2022-09-25 10:28 41阅读 0赞

[数据结构实验之图论五：从起始点到目标点的最短步数（BFS）][BFS]

#include <bits/stdc++.h>
    using namespace std;
    int vis[1110];
    int map1[1100][1100];
    int k,m;
    struct node
    {
        int x,y,ans;
    }q[2100];
    int bfs(int x)
    {
        int e=0,s=0,i;
        struct node t,f;
        t.x=x,t.ans=0;
        q[e++]=t;
        vis[t.x]=1;
        while(s<e)
        {
            t=q[s++];
            if(t.x==1)
            {
                printf("%d\n",t.ans);
                return 0 ;
            }
            for(i=1;i<=k;i++)
            {
                f.x=i;
                if(vis[f.x]==0&&map1[t.x][f.x]==1)
                {
                    f.ans=t.ans+1;
                    q[e++]=f;
                    vis[f.x]=1;
                }
            }
        }
      printf("NO\n");
      return  0;
    }
    int main()
    {
        while (~scanf("%d%d",&k,&m))
        {
            memset (map1,0,sizeof(map1));
            memset(vis,0, sizeof(vis));
            while(m--)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                map1[x][y]=1;
            }
            bfs(k);
        }
        return 0;
    }

[BFS]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2228/pid/2139.html