AtCoder Beginner Contest D - .. (Double Dots) Difficulty: 750
Ce thème, liste adjacente
La recherche de priorité de largeur est effectuée à partir de la liste adjacente, mais l'itinéraire le plus court est obtenu en enregistrant l'itinéraire à partir de la pièce la plus proche de la pièce 1 et en sautant la pièce enregistrée. 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
Adapté à l'index du tableau commençant par «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])
Vous pouvez obtenir l'itinéraire le plus court avec networkx.shortest_path. ~~ Aucune recherche de priorité de largeur n'est requise ~~
Heureusement, ce problème est «TLE», mais «networkx» est incroyable.
| Ruby | Python | PyPy | Python (networkx) | |
|---|---|---|---|---|
| Longueur du code(Byte) | 335 | 459 | 459 | 321 |
| Temps d'exécution(ms) | 335 | 696 | 451 | TLE |
| Mémoire(KB) | 32748 | 36920 | 94388 | 187248 |
Site référencé networkx Tutorial
Recommended Posts