Ruby と Python と networkx で解く AtCoder ABC168 D 隣接リスト

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest D - .. (Double Dots)
Difficulty: 750

今回のテーマ、隣接リスト

隣接リストから幅優先探索をするのですが、部屋１に近い部屋から道しるべを記録し、記録した部屋をスキップすることにより最短経路を取得します。

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

配列のインデックスが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])

networkx.shortest_pathで最短経路が取得できます。幅優先探索なんていりません
幸い、この問題ではTLEになりますが、networkx凄いですね。

	Ruby	Python	PyPy	Python (networkx)
コード長 (Byte)	335	459	459	321
実行時間 (ms)	335	696	451	TLE
メモリ (KB)	32748	36920	94388	187248

まとめ

• ABC 168 D を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• networkx に詳しくなった

参照したサイト
networkx Tutorial
Python3 キュー操作 (collections.deque)
PythonでABC168Dを解く