AtCoder Beginner Contest D - .. (Double Dots) Difficulty: 750
Dieses Thema, nebenstehende Liste
Die Suche nach der Breite der Priorität wird aus der nebenstehenden Liste durchgeführt. Die kürzeste Route wird jedoch erhalten, indem die Route aus dem Raum, der Raum 1 am nächsten liegt, aufgezeichnet und der aufgezeichnete Raum übersprungen wird. 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
Angepasst an den Index des Arrays beginnend mit "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])
Sie können die kürzeste Route mit networkx.shortest_path erhalten. ~~ Es ist keine Suche nach Breitenpriorität erforderlich ~~
Glücklicherweise ist dieses Problem "TLE", aber "networkx" ist erstaunlich.
| Ruby | Python | PyPy | Python (networkx) | |
|---|---|---|---|---|
| Codelänge(Byte) | 335 | 459 | 459 | 321 |
| Ausführungszeit(ms) | 335 | 696 | 451 | TLE |
| Erinnerung(KB) | 32748 | 36920 | 94388 | 187248 |
Referenzierte Site networkx Tutorial
Recommended Posts