[GO] Dyxtra-Methode: Ich habe das Problem von AOJ mit Python anhand des Inhalts von Kencho-sans Artikel in der Oktober-Ausgabe von Software Design gestellt.

Problem gelöst

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A

Quelle

• Beachten Sie, dass für das AOJ-Problem ein Startpunkt angegeben wurde
• In Arimoto wurde ein Flag verwendet, um nach Updates zu suchen. Kenchons Methode besteht jedoch darin, zu bestätigen, ob es nicht aktualisiert wurde (nicht in die Prioritätswarteschlange stellen).
• Suchen Sie aus den Scheitelpunkten (den Scheitelpunkten mit dem kürzesten Abstand vom Start), die Sie erhalten, indem Sie die Prioritätswarteschlange öffnen.

import heapq
INF = 10**10

class Edge:
    to = -1
    w = -1
    def __init__(self, to, w):
        self.to = to
        self.w = w

def Dijkstra(Graph, s):
    dist = [INF] * len(Graph)
    dist[s] = 0

    prev = [-1] * len(Graph)

    #Stellt den Startscheitelpunkt in die Warteschlange
    #[Kürzeste Entfernung zum entsprechenden Peak (aktuelle Zeit),Index des entsprechenden Scheitelpunkts]
    que = [[0,s]]

    #In eine Prioritätswarteschlange konvertieren
    heapq.heapify(que)

    while len(que) > 0:
        #Rufen Sie das erste Element einer priorisierten Warteschlange ab
        #v ist die Scheitelpunktnummer,d ist der aktuell kürzeste Abstand zum entsprechenden Scheitelpunkt
        p = heapq.heappop(que)
        v = p[1]
        d = p[0]

        #Beim Software-Design gibt es die folgende Verarbeitung, aber ist sie nicht erforderlich?
        #Ich verstehe die Notwendigkeit nicht wirklich
        #if d > dist[v]:
        #   continue

        #Berechnen Sie den Abstand für jeden Scheitelpunkt, der vom entsprechenden Scheitelpunkt v erreicht werden kann
        for e in Graph[v]:
            #Wenn die kürzeste Entfernung nicht aktualisiert werden kann, tun Sie nichts
            if dist[v] + e.w >= dist[e.to] :
                continue

            #Das Folgende ist, wenn die kürzeste Entfernung aktualisiert werden kann

            #Verschieben Sie die Zielscheitelpunktinformationen in eine Prioritätswarteschlange
            heapq.heappush(que,[dist[v] + e.w, e.to])

            #Aktualisieren Sie die kürzeste Zielentfernung
            dist[e.to] = dist[v] + e.w

            #Merken Sie sich den Knoten vor dem Ziel
            #Wird nicht für AOJ-Probleme verwendet
            prev[e.to] = v

    for d in dist:
        if d == INF:
            print("INF")
        else:
            print(d)

    return

def main():
    n, m, s = map(int, input().split())
    Graph =  [[] for j in range(n)]
    for i in range(m):
        a, b, w = map(int, input().split())
        Graph[a].append(Edge(b, w))
        #AOJ Problem ist gültige Grafik (http)://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A）
        #Graph[b].append(Edge(a, w))

    Dijkstra(Graph, s)

main()