Lösen Sie mit Python [100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten] (056 - 059 Problem mit der kürzesten Route: Dyxtra-Methode)

1. Zweck

Lösen Sie 100 frühere Fragen, die Anfänger und Fortgeschrittene lösen sollten in Python. Das Ziel ist es, hellblau zu werden, wenn Sie alles gelöst haben.

Dieser Artikel ist "056 - 059 Problem der kürzesten Route: Dyxtra-Methode".

2. Zusammenfassung

Ich habe die Dyxtra-Methode und die Worshall Floyd-Methode verstanden, indem ich mir den Kanal von Abdul Bari auf YouTube angesehen habe. Es war sehr leicht zu verstehen und ich löste das Problem, nachdem ich das Video angesehen und den Algorithmus verstanden hatte, sodass ich reibungslos vorgehen konnte.

3. Hauptgeschichte

056 --059 Problem mit der kürzesten Route: Dyxtra-Methode

056. GRL_1_A - Einzelstartpunkt kürzeste Route

Antworten

import heapq
#--------------------------------------[Eingangsbeleg]--------------------------------------#
INF = float('inf')
V, E, r = map(int, input().split())
graph = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    graph[s].append((t, d))
#--------------------------------------[Ursprünglicher Wert]--------------------------------------#
dp = [INF] * V
visited = [-1] * V
dp[r] = 0
h = [(0, r)]
#--------------------------------------[Beginnen Sie mit der Erkundung]--------------------------------------#
while h:
    d, s = heapq.heappop(h) #Auszug in aufsteigender Reihenfolge der Kosten
    if visited[s] == 1:
        continue
    visited[s] = 1
    targets = graph[s]
    for target in targets:
        t, d = target
        if dp[t] > dp[s] + d:
            dp[t] = dp[s] + d
            heapq.heappush(h, (dp[t], t))
#--------------------------------------[Antworten]--------------------------------------#
for answer in dp:
    if answer == INF:
        print('INF')
    else:
        print(answer)

Holen Sie den Haufen in aufsteigender Reihenfolge. Der Algorithmus ist leicht zu verstehen 3.6 Dijkstra-Algorithmus - Single Source Shortest Path - Greedy-Methode. Die Antwort lautet, wenn Sie es wie in diesem Video erläutert in den Code einfügen.

057. JOI 2008 Qualifying 6 - Schiffsreise

Antworten

import heapq

def cal_cost(graph, n, start, end):
    #--------------------------------------[Ursprünglicher Wert]--------------------------------------#
    dp = [INF] * (n + 1)
    visited = [-1] * (n + 1)
    dp[start] = 0
    h = [(0, start)]
    #--------------------------------------[Beginnen Sie mit der Erkundung]--------------------------------------#
    while h:
        _, s = heapq.heappop(h) #s ist Start,e ist das Ende
        if visited[s] == 1:
            continue
        visited[s] = 1
        targets = graph[s]

        for target in targets:
            cost, e = target
            if dp[e] > dp[s] + cost:
                dp[e] = dp[s] + cost
                heapq.heappush(h, (dp[e], e))

    return dp[end]


if __name__ == "__main__":
    INF = float('inf')
    n, k = map(int, input().split()) #n ist die Anzahl der Inseln, k ist die Anzahl der Zeilen für die folgende Eingabe
    graph = [[] for _ in range(n+1)] #1 Index

    answer_list = []
    for _ in range(k):
        info_list = list(map(int, input().split()))

        if info_list[0] == 1:
            island_1, island_2, cost = info_list[1], info_list[2], info_list[3]
            graph[island_1].append((cost, island_2))
            graph[island_2].append((cost, island_1))
        else:
            start, end = info_list[1], info_list[2]
            answer = cal_cost(graph, n, start, end)
            answer_list.append(answer)
 
    for answer in answer_list:
        if answer == INF:
            print(-1)
        else:
            print(answer)

Es ist eine etwas andere Version von Frage 56, aber im Grunde ist es dasselbe. Insbesondere ist der Inhalt von `` cal_cost () `fast identisch, sodass Sie ihn lösen können, wenn Sie nur auf den Empfang der Eingabe achten.

058. JOI 2016 Qualifying 5 - Zombie Island

Antworten

from collections import deque
import heapq
#--------------------------------------[Ursprünglicher Wert]--------------------------------------#
INF = float('inf')
N, M, K, S = map(int, input().split()) #N Städte, M Straßen, K von Zombies dominiert, gefährliche Städte innerhalb von S von Zombies
P, Q = map(int, input().split()) #P Yen wenn nicht gefährlich, Q Yen wenn gefährlich
zombie_towns = [int(input()) for _ in range(K)]

graph = [[] for _ in range(N+1)]
for _ in range(M):
    townA, townB = map(int, input().split())
    graph[townA].append((INF, townB))
    graph[townB].append((INF, townA))

#--------------------------------------[Erkunde die Entfernung von Zombie Town mit BFS]--------------------------------------#
# zombie_BFS, um gefährliche Städte innerhalb von S aus Städten zu finden
visited = [INF] * (N+1)
q = deque()
for zombie_town in zombie_towns:
    q.append(zombie_town)
    visited[zombie_town] = 0

while q:
    start_town = q.popleft()

    for target in graph[start_town]:
        _, end_town = target
    
        if visited[end_town] != INF:
            continue
        q.append(end_town)
        visited[end_town] = visited[start_town] + 1

# zombie_Rekord als Set für gefährliche Städte innerhalb von S aus Städten
cost_Q = set()
for i in range(1, N+1):
    if visited[i] <= S:
        cost_Q.add(i)

#--------------------------------------[Suchen Sie mit heapq nach der kürzesten Entfernung]]--------------------------------------#
#Haufen drehen
dp = [INF] * (N+1)
visited2 = [-1] * (N+1)
dp[1] = 0
h = [(0, 1)]
answer = 0
while h:
    cost, s = heapq.heappop(h) #s ist Start,e ist das Ende
    if visited2[s] == 1:
        continue
    if s in zombie_towns: #Ich gehe nicht mit Zombies in Städte
        continue
    visited2[s] = 1
    targets = graph[s]

    for target in targets:
        _, e = target

        if e in cost_Q: #  zombie_Q für gefährliche Städte innerhalb von S aus Städten,Davon abgesehen, P.
            cost = Q
        else:
            cost = P

        if dp[e] > dp[s] + cost:
            dp[e] = dp[s] + cost
            heapq.heappush(h, (dp[e], e))
        if e == N: #Wenn das Ziel herauskommt, brechen Sie dort
            answer = dp[s] #Die Antwort sind die Kosten, die unmittelbar vor dem Ziel erfasst wurden
            break
    if answer != 0:
        break

print(answer)

Die Implementierung ist schwer. Wenn Sie jedoch aufschlüsseln, was Sie tun, ist dies leicht zu verstehen, da es sich um eine Kombination der Probleme handelt, die Sie bisher gelöst haben. Die Probleme lassen sich grob in zwei Teile unterteilen: "Finde die Entfernung von der Zombiestadt" und "Finde den Weg der minimalen Kosten".

Um "die Entfernung von der Zombiestadt zu finden", verwenden Sie "BFS", um die kürzeste Entfernung vom Zombie zu ermitteln. Verwenden Sie die Dyxtra-Methode mit `` `heapq```, um den Pfad mit den niedrigsten Kosten zu finden.

059. JOI 2014 Qualifying 5-Taxi

Antwort (TLE (MLE für Pypy))

from collections import deque
import heapq

#------------------[Finden Sie mit BFS die Entfernung von jedem Punkt zu jedem Ziel]----------------------#
def bfs(start, graph):

    visited = [-1] * N
    q = deque()
    q.append(start)
    visited[start] = 0

    while q:
        s = q.popleft()
        targets = graph[s]
        for e in targets:

            if visited[e] != -1:
                continue
            visited[e] = visited[s] + 1
            q.append(e)

    return visited


if __name__ == "__main__":
    #------------------[Eingang]----------------------#
    INF = float('inf')

    N, K = map(int, input().split()) #N Städte, K Straßen
    costs = [INF] * N
    counts = [0] * N
    for i in range(N):
        C, R = map(int, input().split())
        costs[i] = C
        counts[i] = R
        
    graph = [[] for _ in range(N)]
    for _ in range(K):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        graph[A].append(B)
        graph[B].append(A)

    #------------------[Diagramm neu erstellen]]----------------------#
    graph2 = [[] for _ in range(N)]
    for start in range(N):
        end_list = bfs(start, graph)

        for end, count in enumerate(end_list):
            if counts[start] < count: 
                continue
            if start == end:
                continue
            graph2[start].append((costs[start], end)) #Fügen Sie dem Diagramm nur den Teil hinzu, der innerhalb der Anzahl der Male liegen kann
    
    #------------------[Kürzeste Entfernung mit Heapq]]----------------------#
    dp = [INF] * N
    visited = [-1] * N
    dp[0] = 0
    h = [(0, 0)]
    while h:
        _, s = heapq.heappop(h)
        if visited[s] == 1:
            continue
        visited[s] = 1
        targets = graph2[s]

        for target in targets:
            cost, e = target
            if dp[e] > dp[s] + cost:
                dp[e] = dp[s] + cost
                heapq.heappush(h, (dp[e], e))
    
    print(dp[N-1])

Mit dem obigen Code sind 2 von 5 Fällen "TLE". Wenn Sie mit "Pypy" einreichen, ist nur einer der fünf Fälle "MLE".

Die große Idee ähnelt Problem 58, bei dem Sie `` `BFS``` und dann die Dyxtra-Methode ausführen.

Wenn Sie eine Richtlinie schreiben,

1. Berechnen Sie ausgehend von allen Städten anhand von `graph``` mit` bfs```, wie viele Hände Sie zu jeder Stadt gehen können
2. Fügen Sie diese Liste der Schritte in `end_list `ein
3. Erstellen Sie `graph2``` mit` end_list`` und`` count``` mit dem Eingabewert ``R```
4. Wenn Sie `` `graph2``` erstellen können, müssen Sie nur die Dyxtra-Methode ausführen.

ist.

Das in der Problemstellung angegebene `graph``` wird für` bfs verwendet Das rekonstruierte `` `graph2 wird in der Dyxtra-Methode verwendet, Ist das der interessante Teil dieses Problems?