Lösen mit Ruby, Python und networkx AtCoder ABC168 D Benachbarte Liste

Einführung

Dieses Thema

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

Zusammenfassung

Referenzierte Site networkx Tutorial

Recommended Posts

Lösen mit Ruby, Python und networkx AtCoder ABC168 D Benachbarte Liste
Lösen mit Ruby und Python AtCoder ABC138 D Benachbarte Liste
Lösen mit Ruby und Python AtCoder ABC178 D Dynamische Planungsmethode
Lösen mit Ruby und Python AtCoder ABC151 D Suche nach Breitenpriorität
AtCoder ABC 165 D Bodenfunktion in Ruby, Perl, Java und Python gelöst
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 131 D Sortieren von Arrays
Lösen mit Ruby und Python AtCoder ABC133 D Kumulative Summe
Lösen mit Ruby und Python AtCoder AISING2020 D Iterative Square-Methode
Lösen mit Ruby und Python AtCoder ABC153 E Dynamische Planungsmethode
Lösen in Ruby, Python und Java AtCoder ABC141 D Priority Queue
Lösen mit Ruby, Python und numpy AtCoder ABC054 B Matrixberechnung
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 065 C-te Potenz
Lösen mit Ruby und Python AtCoder ABC057 C Zerlegung des Primfaktors Bit vollständige Suche
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 107 B String-Manipulation
Lösen mit Ruby und Python AtCoder ABC084 D Kumulative Summe der Primzahlen
Lösen mit Ruby und Python AtCoder ARC 059 C Minimum-Quadrat-Methode
Lösen mit Ruby, Perl, Java und Python AtCoder ATC 002 A.
Lösen mit Ruby und Python AtCoder ARC067 C Primfaktorisierung
Lösen mit Ruby, Perl, Java und Python AtCoder ATC 002 B.
Löse AtCoder ABC168 mit Python (A ~ D)
AtCoder ABC110 C-String-Manipulation zum Lösen in Ruby
AtCoder ABC130 D Kumulative Summen-Dichotomie, gelöst durch Ruby und Python
Lösen mit Ruby, Perl, Java und Python AtCoder AGC 033 Eine Suche mit Breitenpriorität
Lösen mit Ruby, Perl, Java und Python AtCoder ARC 098 C Kumulative Summe
Lösen mit Ruby, Perl, Java und Python AtCoder CADDi 2018 C Primfaktorisierung
Lösen mit Ruby und Python AtCoder Tenka1 Programmer Contest C Kumulative Summe
Lösen mit Ruby, Perl, Java und Python AtCoder ABC 047 C Regulärer Ausdruck
Löse AtCoder ABC166 mit Python
AtCoder ARC080 D Simulation mit Ruby und Python gelöst
Lösen mit Ruby und Python AtCoder CODE FESTIVAL 2016 qual C B Priority Queue
AtCoder ABC 182 Python (A ~ D)
Lösen mit Ruby, Perl, Java und Python AtCoder diverta 2019 Programmierwettbewerb C String Manipulation
AtCoder ABC155 Problem D Pairs Review Note 2 NumPy und Python
AtCoder ABC168 Ein in Ruby und Python gelöster Fallausdruck
Scraping mit Node, Ruby und Python
Löse ABC166 A ~ D mit Python
AtCoder ABC 114 C-755 mit Python3 gelöst
AtCoder ARC104 B Kumulative Summe in Ruby, Python und Java gelöst
[AtCoder] Löse ABC1 ~ 100 Ein Problem mit Python
Mit Ruby (Rails) verschlüsseln und mit Python entschlüsseln
Einfaches Web-Scraping mit Python und Ruby
Lösen mit Ruby und Python AtCoder ABC172 C Kumulative Summen-Dichotomie
AtCoder ABC 174 Python
AtCoder ABC 175 Python
[AtCoder] Lösen Sie ein Problem von ABC101 ~ 169 mit Python
Lösen des Lorenz 96-Modells mit Julia und Python
Fordern Sie AtCoder (ABC) 164 mit Python heraus! A ~ C Problem
[Erklärung zum AtCoder] Kontrollieren Sie die A-, B-, (C), D-Probleme von ABC165 mit Python!
[AtCoder-Erklärung] Kontrollieren Sie die A-, B-, C- und D-Probleme von ABC183 mit Python!
Lösen mit Ruby, Perl, Java und Python AtCoder ARC 066 C Iterativer Square Hash
[Erklärung zum AtCoder] Kontrollieren Sie die A-, B-, C- und D-Probleme von ABC181 mit Python!
Löse AtCoder 167 mit Python
Ruby, Python und Map
Vergleich von CoffeeScript mit JavaScript-, Python- und Ruby-Grammatik
Versionsverwaltung von Node, Ruby und Python mit anyenv
Liste mit Python initialisieren
AtCoder JSC2019 Qual B Gelöst von Ruby und Python
[AtCoder Erklärung] Kontrollieren Sie ABC180 A, B, C Probleme mit Python!
[AtCoder Erklärung] Kontrollieren Sie ABC158 A, B, C Probleme mit Python!