SHARE
TWEET

Untitled

a guest Dec 10th, 2018 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import sys
  2. sys.setrecursionlimit(0x10000000)
  3.  
  4.  
  5. def add(a, b):
  6.     g[a].append(b)
  7.     g[b].append(a)
  8.  
  9.  
  10. def bfs(st):
  11.     q = []
  12.     q.append(st)
  13.     used[st] = True
  14.     while len(q) != 0:
  15.         v = q.pop(0)
  16.         for i in g[v]:
  17.             if not used[i]:
  18.                 used[i] = True
  19.                 q.append(i)
  20.                 parent[i] = v
  21.                 d[i] = d[v] + 1
  22.  
  23.  
  24. n = int(input())
  25. used = [False] * (n + 10)
  26. parent = [-1] * (n + 10)
  27. d = [0] * n
  28. g = []
  29. for i in range(n):
  30.     g.append([])
  31. for i in range(n):
  32.     l = list(map(int, input().split()))
  33.     for j in range(i + 1, n):
  34.         if l[j] == 1:
  35.             add(i, j)
  36. st, en = list(map(int, input().split()))
  37. bfs(st - 1)
  38. if not used[en - 1]:
  39.     print(-1)
  40. else:
  41.     path = []
  42.     v = en - 1
  43.     while v != -1:
  44.         path.append(v + 1)
  45.         v = parent[v]
  46.     print(len(path) - 1)
  47.     print(*reversed(path))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top