Réponse du livre en spirale AOJ par Python (ALDS1 # 7 ~ # 12)

Dans cet article, nous donnerons des réponses en Python aux sujets # 7 à # 12 du cours ALDS1 (Introduction aux algorithmes et structures de données) du livre en spirale AOJ.

Ceci est une suite de l'article précédent Spiral book in Python, AOJ's answer (ALDS1 # 1 ~ # 6). Veuillez vous référer à cet article pour savoir ce qu'est un livre en spirale / AOJ.

table des matières

répondre

** Arborescence du sujet n ° 7 **

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}")

--Le nœud est représenté comme une classe Node qui contient une référence à l''id du parent pa et une référence aux enfants'chs à l''id`. Au lieu de référencer tous les enfants, le nœud ne peut être représenté que par la référence à l'enfant le plus à gauche et la référence au frère le plus à droite, et n'importe quel arbre peut être traité comme un arbre virtuellement bifurqué. "Représentation gauche-enfant frère droit" (left-child, right-frère representaiton) ", mais je pense que le code est plus facile à lire s'il utilise une référence à tous les enfants.

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}")

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

--La partie ci-dessus def walk est la même que la question précédente 7_B

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)

--Si vous souhaitez simplement afficher la marche Post order, vous pouvez le faire pendant le processus de reconstruction de l'arbre, et vous n'avez pas besoin d'utiliser l'arbre reconstruit, vous n'avez donc pas besoin de créer une instance du nœud.

** Thème n ° 8 Arbre de recherche par bisection **

Dans la liste concaténée, vous pouvez insérer / supprimer (positionné) avec $ O (1) $, mais la recherche coûte $ O (n) $, et vous devez rechercher la suppression par clé, donc $ O (n) Cela coûte $. D'autre part, l'arbre de dichotomie est une structure de données qui vous permet d'insérer, de rechercher et de supprimer tout à $ O (h) $ avec la hauteur de l'arbre comme $ h $. $ h $ est $ O (n) $ dans le pire des cas, mais lorsque vous insérez des éléments aléatoirement pour composer un arbre, il est très rapide à $ O (\ log n) $ en moyenne. La traversée dans l'ordre permet également de visiter les nœuds dans l'ordre de tri des clés à un instant $ \ Theta (n) $.

ALDS1_8_A: Binary Search Tree I Le problème de l'insertion d'éléments dans un arbre de dichotomie. Omis car il est complètement inclus dans le numéro III suivant

ALDS1_8_B: Binary Search Tree II Le problème de l'insertion et de la recherche d'éléments dans l'arbre de dichotomie. Omis car il est complètement inclus dans le numéro III suivant

ALDS1_8_C: Binary Search Tree III Problème d'insertion / recherche / suppression d'éléments dans l'arbre de dichotomie

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))

――L'insertion et la recherche sont comme vous pouvez le voir, c'est facile à comprendre simplement en descendant de la racine à la feuille, mais la suppression est un peu compliquée

――Il peut être géré sans avoir les informations du nœud parent dans chaque nœud. L'insertion et la recherche ne nécessitent pas d'informations sur le nœud parent, uniquement lors de la suppression, mais vous pouvez conserver les informations parentales sur le chemin vers le nœud que vous souhaitez supprimer

En outre, [Colmen "Algorithm Introduction 3rd Edition"](https://www.amazon.co.jp/dp/B078WPYHGN Comme indiqué à la fin du chapitre 12 de), cette méthode de suppression peut poser des problèmes. Avec cette méthode de suppression, si le nœud que vous souhaitez supprimer a deux enfants, les informations de clé d'un autre nœud sont copiées dans l'instance du nœud que vous souhaitez supprimer à l'origine, au lieu de supprimer l'instance du nœud que vous souhaitez supprimer à l'origine. Une instance du nœud sera supprimée. Par conséquent, si vous référencez une instance au lieu d'une clé ailleurs dans votre code, vous pouvez faire référence à un nœud différent du nœud prévu. La solution à ce problème, bien que plus compliquée, consiste à réécrire la partie fonction delete dans un formulaire qui n'utilise pas une copie des informations clés:

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

Un arbre dichotomisé peut être inséré, recherché et supprimé avec la hauteur de l'arbre comme $ h $, le tout avec $ O (h) $, et lors de la construction d'un arbre en insérant des éléments au hasard, $ h $ est en moyenne. $ O (\ log n) $ est très rapide, mais pour le pire ordre d'insertion, ce sera $ O (n) $. Un arbre de recherche dichotomique conçu pour supprimer la valeur attendue ou la pire valeur la plus élevée de la hauteur de l'arbre à $ O (\ log n) $ pour tout ordre d'insertion est appelé un arbre de recherche dichotomique équilibré. Ceci est particulièrement utile pour les algorithmes en ligne où vous ne pouvez pas choisir l'ordre d'insertion.

--L'arbrep est un arbre de dichotomie auquel est assignée au hasard une nouvelle variable, priorité, pour en faire un tas de dichotomie. Cela a pour effet de rendre aléatoire l'ordre d'insertion et la valeur attendue de la hauteur de l'arbre pour tout ordre d'insertion peut être supprimée à $ O (\ log n) $. Cependant, la pire valeur est $ O (n) $

――Les arbres de recherche dichotomiques équivalents qui suppriment fortement la pire valeur de hauteur d'arbre à $ O (\ log n) $ incluent les arbres rouges et noirs (arbres bicolores), mais ils sont plus compliqués.

** Thème n ° 9 Tas **

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 Si vous écrivez vous-même max_heapify,

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)

--Dans max_heapify, considérons un triplet du nœud parent spécifié ʻA [i]et ses enfants ʻA [2 * i + 1], ʻA [2 * i + 2]. Un enfant qui n'existe pas est traité comme $ - \ infty $. Si le nœud parent est plus petit que le nœud enfant, remplacez le nœud parent par le nœud enfant le plus grand, puis récursivement max_heapify` sur ce nœud enfant.

Avec le module heapq:

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 Si j'écris ʻextract ou ʻinsert par moi-même comme ci-dessous, cela devient 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))

Apparemment, il semble que vous deviez inventer beaucoup, donc si vous abandonnez et utilisez le module heapq, cela passera:

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))

** Thème n ° 10 Planification dynamique **

Il existe deux types de méthodes de planification dynamique: une méthode descendante qui utilise la récurrence mémorielle et une méthode ascendante qui résout explicitement les problèmes partiels dans l'ordre croissant.

――D'un autre côté, la méthode ascendante a l'inconvénient de devoir penser à l'ordre ascendant, mais vous pouvez économiser la quantité de calcul spatial lorsque le résultat du calcul du problème partiel peut être écarté au milieu comme le problème du nombre de Fibonacci ci-dessous. Il y a un mérite qui peut être fait

ALDS1_10_A: Fibonacci Number Dans la méthode descendante:

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())))

Dans la méthode ascendante:

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

ALDS1_10_B: Matrix Chain Multiplication

Dans la méthode descendante:

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))

Dans la méthode ascendante:

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])

--Remplir le résultat du calcul n_mul [i] [j] du problème partiel dans l'ordre croissant de la taille $ l = j-i $ du problème partiel.

ALDS1_10_C: Longest Common Subsequence En Python, la méthode naturelle suivante sera TLE au milieu, que ce soit de haut en bas ou de bas en haut. Montant du calcul des deux tempsO(q|X||Y|)Est.

Dans la méthode descendante:

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)))

Au format ascendant:

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])

Au format ascendantiChacun dans une boucle suriContrel[i+1][:]Je calcule, mais c'est juste avantiRésultat du calcull[i][:]Je ne l'utilise que. pour cette raison,l[i][:]Variables temporairesl[:]Stocker dansiMis à jour à chaque fois, passéiDansl[i][:]En ignorant les valeurs de, la quantité de calcul spatialO(|X||Y|)DeO(|Y|)Peut être réduit à. Parallèlement à cela, le temps de calcul ne change pas, mais l'ordre est doublé par une constante et passe sans TLE:

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()))

Si ce code est réécrit sous la forme ci-dessous sans définir la fonction lcs, il sera TLE même s'il doit avoir le même contenu. Je ne comprends pas pourquoi réécrire la fonction pour la définir réduirait la quantité de calcul. Si quelqu'un peut le comprendre, je vous serais reconnaissant de bien vouloir me le faire savoir.

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

** Thème n ° 11 Graphique I **

En tant qu'algorithme de recherche de graphe principal qui recherche tous les sommets du graphe le long des arêtes, la recherche de priorité de profondeur (Depth First Search; DFS) qui recherche les sommets visités avec Last In et First Out comme une pile. , Il existe une recherche de priorité de largeur (Breadth First Search; BFS) qui recherche les sommets visités avec First In et First Out comme une file d'attente. Il peut être utilisé indépendamment du fait que le graphe soit dirigé ou non.

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)

--Dans la représentation de liste adjacente, le montant du calcul spatial de $ O (E + V) $ est suffisant, mais il faut le temps du calcul du temps de la recherche de liste pour déterminer s'il existe un côté entre les deux sommets spécifiés. D'autre part, bien que la représentation matricielle adjacente nécessite un montant de calcul spatial de $ O (V ^ 2) $, le calcul du temps de $ O (1) $ est utilisé pour déterminer s'il y a ou non un côté entre les deux sommets spécifiés. Cela ne coûte que très cher.

Dans ce code, la matrice adjacente ʻA` est spécifiquement construite, mais dans ce problème, il semble que les sommets ne soient en fait saisis que dans l'ordre à partir de 1, et cela passe même si le traitement d'entrée / sortie est effectué ligne par ligne sans créer de matrice.

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])

--Bien que vous puissiez écrire en utilisant la pile, écrire en utilisant une récursive comme celle-ci simplifie le code.

--Les trois types d'états suivants pour chaque sommet

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")

** Thème n ° 12 Graphique 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)

――Le temps de calcul de ces algorithmes dépend de la manière d'implémenter la structure de données utilisée dans chaque algorithme, mais il peut être réalisé de manière linéaire logarithmique par rapport à la taille du graphique. L'algorithme de Kruskal peut atteindre $ O (E \ log V) $ dans certaines implémentations, en fonction de la manière dont il implémente un ensemble de tribus qui s'excluent mutuellement. Selon la façon dont la file d'attente priorisée est implémentée dans l'algorithme de Prim, $ O (E \ log V) $ peut être réalisé en l'implémentant avec un tas de 2 minutes comme ce code. Cela peut être amélioré en $ O (E + V \ log V) $ en utilisant le tas de Fibonacci. Il s'agit d'une amélioration car $ V = O (E) $ plutôt que $ V-1 \ le E $ dans le graphe concaténé. Pour les graphes généraux, $ V = \ Omega (E ^ {1/2}) $, et si $ V $ est $ o (E) $, c'est une vraie amélioration.

--Cependant, dans ce code, en utilisant la représentation de matrice de contiguïté au lieu de la représentation de liste de contiguïté, l'instruction for qui s'étend sur le tas est exécutée pour chaque élément extrait du tas, et la taille du tas est grande. Considérant que le maximum est $ V $, il semble que l'ordre du montant du calcul s'aggrave car il contribue $ O (V ^ 2) $ au montant du calcul.

--Construisez le tas minimum tas composé du coût supplémentaire de chaque nœud, retirez le nœud avec le coût supplémentaire le plus petit et ajoutez le coût aux poids totaux poids. Afin de mettre à jour le coût supplémentaire des nœuds v adjacents au nœud extrait u, non seulement le coût supplémentaire du nœud extrait w mais également les informations sur le nœud u qui a été extrait sont nécessaires, ils sont donc ajoutés au tas Contient une liste «[w, u]» composée d'un coût supplémentaire «w» et d'un numéro de nœud «u». En Python, les comparaisons de listes sont effectuées sous forme de dictionnaire dans l'ordre à partir du premier composant, ainsi heappop peut récupérer correctement le nœud de coût minimum [w, u].

--Bien qu'il ne puisse pas être utilisé avec AOJ, dans un environnement où scipy peut être utilisé tel qu'AtCoder, l'arborescence de la surface totale minimale peut être obtenue en utilisant la fonction scipy.sparse.csgraph.minimum_spanning_tree () sans écrire le code vous-même.

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

Ces deux problèmes sont les mêmes à l'exception de la taille d'entrée et de la limite de temps. Le problème du chemin le plus court du point de départ unique est défini pour un graphe orienté pondéré, et il n'y a pas de solution lorsqu'il existe un chemin fermé négatif (chemin fermé où la somme des poids est négative) qui peut être atteint à partir du point de départ.

--Si le graphe est connu pour être non circulaire ou DAG, il n'y a pas de clôture négative. Dans ce cas, le montant du calcul peut être réduit à $ O (V + E) $ en utilisant le tri topologique.

Je ne sais pas si ce problème est non circulaire, mais je sais que tous les poids sont non négatifs, donc je le résolve avec l'algorithme de Dijkstra. L'algorithme de Dijkstra est similaire à l'algorithme de Prim de l'arborescence de l'aire entière minimale précédente, et détermine le chemin le plus court et sa distance $ d $ dans l'ordre du sommet le plus proche du point de départ avec la distance $ d $. Chaque fois qu'elle est confirmée, la distance $ d $ de chaque sommet qui contient chaque côté qui sort du sommet confirmé est mise à jour si elle peut être mise à jour prochainement.

Dans le code suivant, qui est très similaire au code de l'algorithme de Prim pour le problème d'arborescence de l'aire entière minimale ci-dessus, je peux être résolu mais II devient 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])

Le problème est que la partie $ O (V ^ 2) $ exécute l'instruction for dans le tas pour chaque nœud ʻu` récupéré du tas.

Sur la base de ce qui précède, si vous réécrivez comme ci-dessous, II passera également:

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

Réponse du livre en spirale AOJ par Python (ALDS1 # 7 ~ # 12)
mixeur, python, escalier en colimaçon
livre de recettes python Memo
Résolvez le livre en spirale (algorithme et structure de données) avec python!
mixeur, python, escalier en colimaçon, couleur