Editorial for Path Reconstruction
Use this editorial only when stuck, and do not copy-paste code from it.
Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.
Approach
Because all edges have equal weight, BFS from s finds shortest paths by number of edges.
To break ties lexicographically, sort every adjacency list in increasing order before the BFS. The BFS queue then visits paths of the same length in lexicographic order. Therefore, the first time a vertex is reached, the stored parent gives the lexicographically smallest shortest path to that vertex.
After BFS, if t has no parent, it is unreachable. Otherwise, follow parent pointers backward from t to s, reverse the sequence, and print it.
The time complexity is O(n+mlogm) due to sorting the adjacency lists, and the BFS itself is O(n+m).
Implementation
from collections import deque
import sys
def main() -> None:
data = list(map(int, sys.stdin.buffer.read().split()))
if not data:
return
n, m, s, t = data[:4]
graph = [[] for _ in range(n + 1)]
idx = 4
for _ in range(m):
a = data[idx]
b = data[idx + 1]
idx += 2
graph[a].append(b)
graph[b].append(a)
for neighbors in graph:
neighbors.sort()
parent = [-1] * (n + 1)
parent[s] = 0
q = deque([s])
while q:
node = q.popleft()
if node == t:
break
for neighbor in graph[node]:
if parent[neighbor] == -1:
parent[neighbor] = node
q.append(neighbor)
if parent[t] == -1:
print(-1)
return
path = []
node = t
while node != 0:
path.append(node)
node = parent[node]
path.reverse()
print(len(path) - 1)
print(*path)
if __name__ == "__main__":
main()
Comments0
No comments yet
Be the first to comment.
New comment
Log in to join the discussion.