AtCoder Beginner Contest D - .. (Double Dots) Difficulty: 750
This theme, adjacency list
Breadth-first search is performed from the adjacency list, but the shortest route is obtained by recording the route from the room closest to room 1 and skipping the recorded room. Ruby
ruby.rb
n, m = gets.split.map(&:to_i)
a = Array.new(n){[]}
m.times do
x, y = gets.split.map(&:to_i)
a[x - 1] << y - 1
a[y - 1] << x - 1
end
c = Array.new(n){0}
que = []
que << 0
while que.size > 0
e = que.shift
a[e].each do |i|
next if c[i] > 0
c[i] = e + 1
que << i
end
end
puts "Yes", c[1..-1]
index.rb
a[x - 1] << y - 1
a[y - 1] << x - 1
Adapted to array indexes starting at 0.
Python
pypy.py
from collections import deque
n, m = map(int, input().split())
a = [[] for _ in range(n)]
for i in range(m):
x, y = map(int, input().split())
a[x - 1].append(y - 1)
a[y - 1].append(x - 1)
c = [0] * n
que = deque([])
que.append(0)
while len(que) > 0:
e = que.popleft()
for i in a[e]:
if c[i] > 0:
continue
c[i] = e + 1
que.append(i)
print("Yes")
for i in range(1, n):
print(c[i])
Python (networkx)
networkx.py
import networkx
n, m = map(int, input().split())
g = networkx.Graph()
g.add_nodes_from(list(range(n)))
for i in range(1, m + 1):
a, b = map(int, input().split())
g.add_edge(a, b)
#print(g.nodes())
#print(g.edges())
print("Yes")
for i in range(2, n + 1):
print(networkx.shortest_path(g, 1, i)[-2])
shortest_path.py
print(networkx.shortest_path(g, 1, i)[-2])
You can get the shortest path with networkx.shortest_path. ~~ No breadth-first search is required ~~
Fortunately, this problem is TLE, but networkx is amazing.
| Ruby | Python | PyPy | Python (networkx) | |
|---|---|---|---|---|
| Code length(Byte) | 335 | 459 | 459 | 321 |
| Execution time(ms) | 335 | 696 | 451 | TLE |
| memory(KB) | 32748 | 36920 | 94388 | 187248 |
Referenced site networkx Tutorial
Recommended Posts