摘要
Title: 847. 图中点的层次
Tag: BFS
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

847. 图中点的层次

• 题意

  给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
  所有边的长度都是 1，点的编号为 1∼n。
  请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

• 思路

  BFS即可

  ---

  模板

  def bfs(s):
        q = deque()
        q.appendleft(s)
        st[s] = 1
        while q:
            u = q.pop()
            for j in g[u]:
                if st[j] == 0:
                    q.appendleft(j)
                    st[j] = 1

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-02 20:23:50
  FilePath: \ACM\Acwing\847.py
  LastEditTime: 2022-03-02 20:29:23
  '''
  
  from collections import deque
  
  N = int(1e5 + 10)
  g = [[] for _ in range(N)]
  st = [0] * N
  
  
  def bfs(s):
      q = deque()
      q.appendleft([s, 0])
      st[s] = 1
      while q:
          t = q.pop()
          u, cnt = t
          if u == n:
              return cnt
          for j in g[u]:
              if st[j] == 0:
                  q.appendleft([j, cnt + 1])
                  st[j] = 1
      return -1
  
  n, m = map(int, input().split())
  for i in range(m):
      a, b = map(int, input().split())
      g[a].append(b)
  
  print(bfs(1))