[GO] Antwort des Spiralbuchs AOJ von Python (ALDS1 # 7 ~ # 12)

In diesem Artikel geben wir in Python Antworten auf die Themen 7 bis 12 des ALDS1-Kurses (Einführung in Algorithmen und Datenstrukturen) des Spiralbuchs AOJ.

Dies ist eine Fortsetzung des vorherigen Artikels Spiralbuch in Python, AOJs Antwort (ALDS1 # 1 ~ # 6). In diesem Artikel finden Sie Informationen zu einem Spiralbuch / AOJ.

Inhaltsverzeichnis

Antworten

** Thema # 7 Baumstruktur **

ALDS1_7_A: Rooted Trees

class Node:
  def __init__(self, pa=-1, chs=None):
    self.pa = pa
    self.chs = chs

n = int(input())
tree = {id:Node() for id in range(n)}
for _ in range(n):
  id, _, *chs = map(int, input().split())
  tree[id].chs = chs
  for ch in chs:
    tree[ch].pa = id

def set_depths(id, depth):
  tree[id].depth = depth
  for ch in tree[id].chs:
    set_depths(ch, depth+1)

for id in tree:
  if tree[id].pa == -1:
    set_depths(id, 0)
    break

for id, node in tree.items():
  kind = "root" if node.pa == -1 else "internal node" if node.chs else "leaf"
  print(f"node {id}: parent = {node.pa}, depth = {node.depth}, {kind}, {node.chs}")

ALDS1_7_B: Binary Trees

class Node:
  def __init__(self, chs, pa=-1):
    self.chs = chs
    self.pa = pa

n = int(input())
tree = {id:Node(chs=[-1,-1]) for id in range(-1, n)}
for _ in range(n):
  id, *chs = map(int, input().split())
  tree[id].chs = chs
  for ch in chs:
    tree[ch].pa = id

def set_d_and_h(id, d):
  tree[id].d = d
  h = 0
  for ch in tree[id].chs:
    if ch != -1:
      h = max(h, set_d_and_h(ch, d+1) + 1)
  tree[id].h = h
  return h

for id in tree:
  if tree[id].pa == -1:
    set_d_and_h(id, 0)
    break

for id, node in tree.items():
  if id != -1:
    sib = tree[node.pa].chs[1] if tree[node.pa].chs[0] == id else tree[node.pa].chs[0]
    deg = 2 - node.chs.count(-1)  
    kind = "root" if node.pa == -1 else "internal node" if deg else "leaf"
    print(f"node {id}: parent = {node.pa}, sibling = {sib}, degree = {deg}, depth = {node.d}, height = {node.h}, {kind}")

--Wenn keine Kinder vorhanden sind, wird es als -1 ausgedrückt und eingegeben. Um auch in diesem Fall eine Schleife um das Kind zu erstellen, wird dem Baum auch ein Knoten hinzugefügt, dessen "id" -1 entspricht, und zwar als sogenannte Wache. Es gibt. Eltern-Kind-Informationen für Knoten mit der ID -1 werden niemals verwendet

ALDS1_7_C: Tree Walk

class Node:
  def __init__(self, chs, pa=-1):
    self.chs = chs
    self.pa = pa

n = int(input())
tree = {id:Node(chs=[-1,-1]) for id in range(-1, n)}
for _ in range(n):
  id, *chs = map(int, input().split())
  tree[id].chs = chs
  for ch in chs:
    tree[ch].pa = id

def walk(id, order):
  walked = ""
  if id != -1:
    if order == "Pre":
      walked += f" {id}"
    walked += walk(tree[id].chs[0], order)
    if order == "In":
      walked += f" {id}"
    walked += walk(tree[id].chs[1], order)
    if order == "Post":
      walked += f" {id}"
  return walked

for id in tree:
  if tree[id].pa == -1:
    for order in ["Pre", "In", "Post"]:
      print(order + "order\n" + walk(id, order))      
    break

ALDS1_7_D: Reconstruction of a Tree

_ = int(input())
pr_walk = [*map(int, input().split())]
in_walk = [*map(int, input().split())]
walked = []

def recon_tree(pr_walk, in_walk):
  if pr_walk:
    root = pr_walk[0]
    i = in_walk.index(root)
    recon_tree(pr_walk[1:i+1], in_walk[:i])
    recon_tree(pr_walk[i+1:], in_walk[i+1:])
    walked.append(root)

recon_tree(pr_walk, in_walk)
print(*walked)

** Thema # 8 Bisection Search Tree **

In der verketteten Liste können Sie mit $ O (1) $ einfügen / löschen (positioniert), aber die Suche kostet $ O (n) $, und Sie müssen nach dem Löschen mit Schlüssel suchen, also $ O (n) Es kostet $. Andererseits ist der Dichotomiebaum eine Datenstruktur, mit der Sie alles bei $ O (h) $ mit der Höhe des Baums als $ h $ einfügen, suchen und löschen können. $ h $ ist im schlimmsten Fall $ O (n) $, aber wenn Sie Elemente zufällig einfügen, um einen Baum zu erstellen, ist es bei $ O (\ log n) $ im Durchschnitt sehr schnell. Durch das Durchlaufen der Reihenfolge können Knoten auch in der Reihenfolge der Schlüsselsortierung zu einem Zeitpunkt von $ \ Theta (n) $ besucht werden.

ALDS1_8_A: Binary Search Tree I Das Problem des Einfügens von Elementen in einen Dichotomiebaum. Ausgelassen, da es in der folgenden III-Ausgabe vollständig enthalten ist

ALDS1_8_B: Binary Search Tree II Das Problem des Einfügens und Suchens nach Elementen im Dichotomiebaum. Ausgelassen, da es in der folgenden III-Ausgabe vollständig enthalten ist

ALDS1_8_C: Binary Search Tree III Problem beim Einfügen / Suchen / Löschen von Elementen in den Dichotomiebaum

class Node:
  def __init__(self, key, left=None, right=None):
    self.key = key
    self.left = left
    self.right = right

def insert(key):
  global root
  if root:
    ch = root
    while ch:
      pa, ch = ch, ch.left if key < ch.key else ch.right
    if key < pa.key:
      pa.left = Node(key)
    else:
      pa.right = Node(key)
  else:
    root = Node(key)

def find(key):
  node = root
  while node and node.key != key:
    node = node.left if key < node.key else node.right
  print("yes" if node else "no")

def delete(key):
  global root
  pa, node = None, root
  while node.key != key:
    pa, node = node, node.left if key < node.key else node.right
  if node.left and node.right:
    pa, to_del = node, node.right
    while to_del.left:
      pa, to_del = to_del, to_del.left
    node.key = to_del.key
  else:
    to_del = node
  ch = to_del.left or to_del.right
  if not pa:
    root = ch
  elif pa.left == to_del:
    pa.left = ch
  else:
    pa.right = ch

def walk(node, order):
  walked = ""
  if node:
    if order == "Pre":
      walked += f" {node.key}"
    walked += walk(node.left, order)
    if order == "In":
      walked += f" {node.key}"
    walked += walk(node.right, order)
  return walked

def show():
  for order in ["In", "Pre"]:
    print(walk(root, order))

root = None
cmds = {"print":show, "insert":insert, "find":find, "delete":delete}
for _ in range(int(input())):
  cmd_name, *key = input().split()
  cmds[cmd_name](*map(int,key))

――Einfügen und Suchen sind, wie Sie sehen können, leicht zu verstehen, wenn Sie nur von der Wurzel zum Blatt gehen, aber das Löschen ist etwas kompliziert

――Wenn es höchstens ein Kind des zu löschenden Knotens gibt, können Sie dieses Kind ("Keine", wenn es kein Kind gibt) einfach zum Kind des Elternteils des Knotens machen, den Sie löschen möchten, sozusagen "wenn das Kind die Ablaufverfolgung erbt". Es ist problematisch, wenn sich zwei Knoten an dem Knoten befinden, den Sie löschen möchten. Wenn Sie beispielsweise versuchen, das richtige Kind erfolgreich zu machen, ist das linke Kind zwei, wenn das rechte Kind bereits ein linkes Kind hat. Erwägen Sie daher, dass ein anderer Knoten erfolgreich ist. Auch nach der Abfolge muss jeder Knoten in der Sortierreihenfolge in der Patrouille mittlerer Ordnung erscheinen. Dies kann jedoch erreicht werden, indem der Knoten unmittelbar vor oder unmittelbar danach in der Patrouille mittlerer Ordnung herausgezogen und ersetzt wird. Hier wird der Knoten unmittelbar danach (der Endpunkt, an dem der Teilbaum rechts weiterhin nach links verfolgt wird) herausgezogen. Da sich unmittelbar vor (kein rechtes Kind) oder unmittelbar danach (kein linkes Kind) höchstens ein Kind am Knoten befindet, ziehen Sie die vorherige Methode aus, wenn höchstens ein Kind vorhanden ist.

――Es kann verwaltet werden, ohne dass die Informationen des übergeordneten Knotens in jedem Knoten vorhanden sind. Für das Einfügen und Suchen sind keine Informationen zum übergeordneten Knoten erforderlich, nur beim Löschen. Sie können jedoch übergeordnete Informationen auf dem Weg zum zu löschenden Knoten beibehalten

Darüber hinaus [Colmen "Algorithm Introduction 3rd Edition"](https://www.amazon.co.jp/dp/B078WPYHGN Wie am Ende von Kapitel 12 von) ausgeführt, kann diese Entfernungsmethode Probleme verursachen. Wenn bei dieser Löschmethode der zu löschende Knoten zwei untergeordnete Knoten hat, werden die Schlüsselinformationen eines anderen Knotens in die Instanz des Knotens kopiert, den Sie ursprünglich löschen möchten, anstatt die Instanz des Knotens zu löschen, den Sie ursprünglich löschen möchten. Eine Instanz des Knotens wird gelöscht. Wenn Sie also auf eine Instanz anstelle eines Schlüssels an einer anderen Stelle in Ihrem Code verweisen, verweisen Sie möglicherweise auf einen Knoten, der sich vom beabsichtigten Knoten unterscheidet. Die Lösung für dieses Problem ist zwar komplizierter, besteht jedoch darin, den Funktionsteil "Löschen" in ein Formular umzuschreiben, in dem keine Kopie der Schlüsselinformationen verwendet wird:

def trans(pa, node, new_node):
  if not pa:
    global root
    root = new_node
  elif pa.left == node:
    pa.left = new_node
  else:
    pa.right = new_node

def delete(key):
  pa, node = None, root
  while node.key != key:
    pa, node = node, node.left if key < node.key else node.right
  if node.left and node.right:
    pa_heir, heir = node, node.right
    while heir.left:
      pa_heir, heir = heir, heir.left
    if pa_heir != node:
      trans(pa_heir, heir, heir.right)
      heir.right = node.right
    trans(pa, node, heir)
    heir.left = node.left
  else:
    trans(pa, node, node.left or node.right)

ALDS1_8_D: Treap

Ein Halbierungssuchbaum kann mit der Höhe des Baums als $ h $ eingefügt, durchsucht und gelöscht werden, alle mit $ O (h) $. Wenn Sie einen Baum durch zufälliges Einfügen von Elementen erstellen, ist $ h $ im Durchschnitt. $ O (\ log n) $ ist sehr schnell, aber für die schlechteste Einfügereihenfolge ist es $ O (n) $. Ein dichotomer Suchbaum, der entwickelt wurde, um den erwarteten Wert oder den stärksten schlechtesten Wert der Baumhöhe für eine beliebige Einfügereihenfolge auf $ O (\ log n) $ zu unterdrücken, wird als ausgeglichener dichotomer Suchbaum bezeichnet. Dies ist besonders nützlich für Online-Algorithmen, bei denen Sie die Einfügereihenfolge nicht auswählen können.

--Der Treep ist ein Dichotomiebaum, dem zufällig eine neue Variable mit Priorität zugewiesen wird, um ihn zu einem Dichotomie-Heap zu machen. Dies bewirkt eine effektive Randomisierung der Einfügereihenfolge, und der erwartete Wert der Baumhöhe für jede Einfügereihenfolge kann auf $ O (\ log n) $ unterdrückt werden. Der schlechteste Wert ist jedoch $ O (n) $

** Thema # 9 Haufen **

ALDS1_9_A: Complete Binary Tree

N = int(input())
heap = input().split()
for i in range(N):
  print(f"node {i+1}: key = {heap[i]}, ", end="")
  print(f"parent key = {heap[(i-1)//2]}, " if i else "", end="")
  print(f"left key = {heap[2*i+1]}, " if 2*i+1 < N else "", end="")
  print(f"right key = {heap[2*i+2]}, " if 2*i+2 < N else "")

ALDS1_9_B: Maximum Heap Wenn Sie selbst "max_heapify" schreiben,

def max_heapify(A, i):
  triad = {j:A[j] if j < N else -float("inf") for j in [i, 2*i+1, 2*i+2]}
  i_max = max(triad, key=triad.get)
  if i != i_max:
    A[i], A[i_max] = A[i_max], A[i]
    max_heapify(A, i_max)

N = int(input())
heap = [*map(int, input().split())]
for i in reversed(range(N//2)):
  max_heapify(heap, i)
print("", *heap)

Mit dem heapq Modul:

from heapq import heapify

_, heap = input(), [-int(x) for x in input().split()]
heapify(heap)
print("", *[-x for x in heap])

ALDS1_9_C: Priority Queue Wenn ich wie unten selbst "extrahieren" oder "einfügen" schreibe, ist dies TLE:

def max_heapify(A, i):
  triad = {j:A[j] if j < len(A) else -float("inf") for j in [i, 2*i+1, 2*i+2]}
  i_max = max(triad, key=triad.get)
  if i != i_max:
    A[i], A[i_max] = A[i_max], A[i]
    max_heapify(A, i_max)

def extract(A):
  print(A[0])
  A[0] = A[-1]
  A.pop()
  max_heapify(A, 0)

def increase_key(A, i, key):
  A[i] = key
  while i and A[(i-1)//2] < A[i]:
    A[(i-1)//2], A[i] = A[i], A[(i-1)//2]
    i = (i-1)//2

def insert(A, key):
  A.append(None)
  increase_key(A, len(A)-1, key)

heap = []
while True:
  op, *key = input().split()
  if op == "end":
    break
  if op == "extract":
    extract(heap)
  else:
    insert(heap, int(*key))

Anscheinend müssen Sie viel entwickeln. Wenn Sie also aufgeben und das heapq -Modul verwenden, wird es passieren:

from heapq import heappop, heappush

heap = []
while True:
  op, *key = input().split()
  if op == "end":
    break
  if op == "extract":
    print(-heappop(heap))
  else:
    heappush(heap, -int(*key))

** Thema Nr. 10 Dynamische Planung **

Es gibt zwei Arten von dynamischen Planungsmethoden: eine Top-Down-Methode, die eine memobasierte Wiederholung verwendet, und eine Bottom-Up-Methode, die Teilprobleme explizit in aufsteigender Reihenfolge löst.

――Die Bottom-Up-Methode hat andererseits den Nachteil, dass Sie über die Reihenfolge von Bottom-Up nachdenken müssen. Sie können jedoch den Umfang der räumlichen Berechnung sparen, wenn das Berechnungsergebnis des Teilproblems in der Mitte wie das Problem der Anzahl der Fibonacci unten verworfen werden kann. Es gibt einen Verdienst, der getan werden kann

ALDS1_10_A: Fibonacci Number In der Top-Down-Methode:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
  if n < 2:
    return 1
  return fib(n-1) + fib(n-2)

print(fib(int(input())))

In der Bottom-Up-Methode:

x = y = 1
for _ in range(int(input())):
  x, y = x + y, x
print(y)

ALDS1_10_B: Matrix Chain Multiplication

In der Top-Down-Methode:

from functools import lru_cache

n = int(input())
p = [int(input().split()[0]) for _ in range(n-1)] + [*map(int, input().split())]

@lru_cache(maxsize=None)
def n_mul(i, j):
  if j - i == 1:
    return 0
  return min(n_mul(i,k) + n_mul(k,j) + p[i]*p[k]*p[j] for k in range(i+1,j))

print(n_mul(0, n))

--Betrachten Sie die Mindestanzahl von Berechnungen für das Produkt $ \ prod_ {k = 0} ^ {n-1} A_k $ der Matrix $ A_k \ in \ text {M} (p_k, p_ {k + 1}) $. n_mul (i, j) löst das Teilproblem $ \ prod_ {k = i} ^ {j-1} A_k $

In der Bottom-Up-Methode:

n = int(input())
p = [int(input().split()[0]) for _ in range(n-1)] + [*map(int, input().split())]

n_mul = [[0]*(n+1) for _ in range(n+1)]
for l in range(2, n+1):
  for i in range(n-l+1):
    j = i + l
    n_mul[i][j] = min(n_mul[i][k] + n_mul[k][j] + p[i]*p[k]*p[j] for k in range(i+1,j))
print(n_mul[0][n])

--Füllen Sie das Berechnungsergebnis n_mul [i] [j] des Teilproblems in aufsteigender Reihenfolge der Größe $ l = j-i $ des Teilproblems.

ALDS1_10_C: Longest Common Subsequence In Python wird die folgende natürliche Methode in der Mitte TLE angezeigt, unabhängig davon, ob sie von oben nach unten oder von unten nach oben erfolgt. Beide ZeitberechnungsbetragO(q|X||Y|)Ist.

In der Top-Down-Methode:

import sys
from functools import lru_cache

sys.setrecursionlimit(100000)

for _ in range(int(input())):
  x, y = input(), input()

  @lru_cache(maxsize=None)
  def lcs(i, j):
    if i == 0 or j == 0:
      return 0
    if x[i-1] == y[j-1]:
      return lcs(i-1, j-1) + 1
    return max(lcs(i-1,j), lcs(i,j-1))

  print(lcs(len(x), len(y)))

Im Bottom-Up-Format:

for _ in range(int(input())):
  x, y = input(), input()
  l = [[0] * (len(y)+1) for _ in range(len(x)+1)]
  for i in range(len(x)):
    for j in range(len(y)):
      l[i+1][j+1] = l[i][j] + 1 if x[i] == y[j] else max(l[i][j+1], l[i+1][j])
  print(l[-1][-1])

Im Bottom-Up-FormatiJeweils in einer Schleife überiGegenl[i+1][:]Ich rechne, aber das ist kurz zuvoriBerechnungsergebnis inl[i][:]Ich benutze es nur. aus diesem Grund,l[i][:]Temporäre Variablenl[:]Speichern iniJedes Mal aktualisiert, vorbeiiIml[i][:]Durch Verwerfen der Werte von wird der Umfang der räumlichen BerechnungO(|X||Y|)VonO(|Y|)Kann auf reduziert werden. Gleichzeitig ändert sich die Zeitberechnung nicht, sie wird jedoch um eine Konstante verdoppelt und ohne TLE vergehen:

def lcs(X, Y):
  l = [0] * (len(Y) + 1)
  for x in X:
    l_pre = l[:]
    for j, y in enumerate(Y):
      if x == y:
        l[j+1] = l_pre[j] + 1
      elif l[j+1] < l[j]:
        l[j+1] = l[j]
  return l[-1]

for _ in range(int(input())):
  print(lcs(input(), input()))

Wenn dieser Code in der folgenden Form umgeschrieben wird, ohne die Funktion "lcs" zu definieren, ist er TLE, obwohl er denselben Inhalt haben sollte. Ich verstehe nicht, warum das Umschreiben der Funktion zur Definition den Rechenaufwand verringern würde. Wenn jemand es verstehen kann, wäre ich dankbar, wenn Sie es mich wissen lassen könnten.

for _ in range(int(input())):
  X, Y = input(), input()  
  l = [0] * (len(Y) + 1)
  for x in X:
    l_pre = l[:]
    for j, y in enumerate(Y):
      if x == y:
        l[j+1] = l_pre[j] + 1
      elif l[j+1] < l[j]:
        l[j+1] = l[j]
  print(l[-1])

ALDS1_10_D: Optimal Binary Search Tree

** Thema Nr. 11 Grafik I **

Als Hauptalgorithmus für die Diagrammsuche, der alle Scheitelpunkte des Diagramms entlang der Kanten durchsucht, die Tiefenprioritätssuche (Depth First Search; DFS), die die besuchten Scheitelpunkte mit Last In und First Out wie ein Stapel durchsucht. , Es gibt eine Breitenprioritätssuche (Breadth First Search; BFS), die die besuchten Scheitelpunkte mit First In und First Out wie eine Warteschlange durchsucht. Es kann unabhängig davon verwendet werden, ob das Diagramm gerichtet oder ungerichtet ist.

ALDS1_11_A: Graph

n = int(input())
A = [[0] * n for _ in range(n)]
for _ in range(n):
  u, _, *V = map(int, input().split())
  for v in V:
    A[u-1][v-1] = 1

for a in A:
  print(*a)

――In diesem Code ist die benachbarte Matrix A speziell konstruiert, aber in diesem Problem scheinen die Eckpunkte tatsächlich nur in der Reihenfolge von 1 eingegeben zu werden. Selbst wenn Sie sich nicht die Mühe machen, eine Matrix zu erstellen und eine Eingabe- / Ausgabeverarbeitung für jede Zeile durchzuführen, wird sie übergeben.

ALDS1_11_B: Depth First Search

n = int(input())
G = [None] * n
for _ in range(n):
  u, _, *V = map(int, input().split())
  G[u-1] = [v-1 for v in V]

d, f = [None] * n, [None] * n
time = 0

def visit(u):
  global time
  time += 1
  d[u] = time
  for v in G[u]:
    if not d[v]:
      visit(v)
  time += 1
  f[u] = time

for u in range(n):
  if not d[u]:
    visit(u)
  print(u+1, d[u], f[u])

ALDS1_11_C: Breadth First Search

n = int(input())
G = [None] * n
for _ in range(n):
  u, _, *V = map(int, input().split())
  G[u-1] = [v-1 for v in V]

d = [0] + [-1] * (n-1)
q = [0]
while q:
  v = q.pop(0)
  for u in G[v]:
    if d[u] == -1:
      d[u] = d[v] + 1
      q.append(u)

for v in range(n):
  print(v+1, d[v])

ALDS1_11_D: Connected Components

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  s, t = map(int, input().split())
  G[s].append(t)
  G[t].append(s)

reps = [None] * n
for s in range(n):
  if reps[s] is None:
    reps[s] = s
    q = [s]
    while q:
      v = q.pop(0)
      for u in G[v]:
        if reps[u] is None:
          reps[u] = s
          q.append(u)

for _ in range(int(input())):
  s, t = map(int, input().split())
  print("yes" if reps[s] == reps[t] else "no")

** Thema Nr. 12 Grafik II **

ALDS1_12_A: Minimum Spanning Tree

from heapq import heapify, heappop

n = int(input())
G = [[*map(int, input().split())] for _ in range(n)]
heap = [[float("inf"), v] for v in range(n)]
heap[0] = [0, 0]
weights = 0
while heap:
  heapify(heap)
  w, u = heappop(heap)
  weights += w
  for i, [w, v] in enumerate(heap):
    if 0 <= G[u][v] < w:
      heap[i] = [G[u][v], v]
print(weights)

――Die Zeitberechnung dieser Algorithmen hängt davon ab, wie die in jedem Algorithmus verwendete Datenstruktur implementiert wird. Sie kann jedoch logarithmisch linear in Bezug auf die Größe des Diagramms realisiert werden. Kruskals Algorithmus kann in einigen Implementierungen $ O (E \ log V) $ erreichen, abhängig davon, wie er eine Reihe von Stämmen implementiert, die sich gegenseitig ausschließen. Abhängig davon, wie die Prioritätswarteschlange im Prim-Algorithmus implementiert ist, kann $ O (E \ log V) $ realisiert werden, indem sie mit einem 2-Minuten-Heap wie diesem Code implementiert wird. Dies kann mithilfe des Fibonacci-Heaps auf $ O (E + V \ log V) $ verbessert werden. Dies ist eine Verbesserung, da $ V = O (E) $ anstelle von $ V-1 \ le E $ im verketteten Diagramm ist. Für allgemeine Graphen ist $ V = \ Omega (E ^ {1/2}) $, und wenn $ V $ $ o (E) $ ist, ist dies eine echte Verbesserung.

ALDS1_12_B: Single Source Shortest Path I ALDS1_12_C: Single Source Shortest Path II

Diese beiden Probleme sind bis auf die Eingabegröße und das Zeitlimit gleich. Das Problem des kürzesten Wegs eines einzelnen Startpunkts ist für einen gewichteten gerichteten Graphen definiert, und es gibt keine Lösung, wenn ein negativer geschlossener Pfad (geschlossener Pfad, bei dem die Summe der Gewichte negativ ist) vom Startpunkt aus erreicht werden kann.

Ich weiß nicht, ob dieses Problem nicht kreisförmig ist, aber ich weiß, dass alle Gewichte nicht negativ sind, also löse ich es mit dem Dijkstra-Algorithmus. Der Dijkstra-Algorithmus ähnelt dem Prim-Algorithmus des vorherigen minimalen Gesamtflächenbaums und bestimmt den kürzesten Pfad und seinen Abstand $ d $ in der Reihenfolge vom Scheitelpunkt, der dem Startpunkt am nächsten liegt, mit dem Abstand $ d $. Jedes Mal, wenn es bestätigt wird, wird der Abstand $ d $ jedes Scheitelpunkts, der jede Seite enthält, die aus dem bestätigten Scheitelpunkt herauskommt, aktualisiert, wenn er in Kürze aktualisiert werden kann.

Im folgenden Code, der dem Code des Prim-Algorithmus für das oben genannte minimale Gesamtflächenbaumproblem sehr ähnlich ist, kann ich gelöst werden, aber II wird zu TLE:

from heapq import heapify, heappop

n = int(input())
G = [None] * n
for _ in range(n):
  u, k, *vc = map(int, input().split())
  G[u] = {vc[2*i]:vc[2*i+1] for i in range(k)}

d = [None] * n
heap = [[float("inf"), v] for v in range(n)]
heap[0] = [0, 0]
while heap:
  heapify(heap)
  d_u, u = heappop(heap)
  d[u] = d_u
  for i, [d_v, v] in enumerate(heap):
    if v in G[u]:
      d_v_new = d_u + G[u][v]
      if d_v > d_v_new:
        heap[i] = [d_v_new, v]

for v in range(n):
  print(v, d[v])

Das Problem ist der $ O (V ^ 2) $ -Teil, der die "for" -Anweisung über den Heap für jeden Knoten "u" aus dem Heap ausführt.

Basierend auf dem oben Gesagten wird II, wenn Sie wie unten umschreiben, auch bestehen:

from heapq import heappop, heappush

n = int(input())
G = [None] * n
for _ in range(n):
  u, k, *vc = map(int, input().split())
  G[u] = {vc[2*i]:vc[2*i+1] for i in range(k)}

d = [0] + [float("inf")] * (n-1)
heap = [[0, 0]]
while heap:
  d_u, u = heappop(heap)
  for v in G[u]:
    d_v = d_u + G[u][v]
    if d[v] > d_v:
      d[v] = d_v
      heappush(heap, [d[v], v])

for v in range(n):
  print(v, d[v])

Recommended Posts

Antwort des Spiralbuchs AOJ von Python (ALDS1 # 7 ~ # 12)
Mixer, Python, Wendeltreppe
Python-Rezeptbuch Memo
Löse das Spiralbuch (Algorithmus und Datenstruktur) mit Python!
Mixer, Python, Wendeltreppe, Farbe