Résoudre avec Python [100 questions passées que les débutants et les intermédiaires devraient résoudre] (056 --059 Problème de l'itinéraire le plus court: méthode Dyxtra)

1. Objet

Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.

Cet article s'intitule "056 - 059 Problème d'itinéraire le plus court: méthode Dyxtra".

2. Résumé

J'ai compris la méthode Dyxtra et la méthode Worshall Floyd en regardant la chaîne de Abdul Bari sur YouTube. C'était très facile à comprendre, et j'ai résolu le problème après avoir regardé la vidéo et compris l'algorithme, donc j'ai pu procéder sans heurts.

3. Histoire principale

056 --059 Problème d'itinéraire le plus court: méthode Dyxtra

056. GRL_1_A - Itinéraire le plus court à point de départ unique

Répondre

import heapq
#--------------------------------------[Reçu d'entrée]--------------------------------------#
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))
#--------------------------------------[valeur initiale]--------------------------------------#
dp = [INF] * V
visited = [-1] * V
dp[r] = 0
h = [(0, r)]
#--------------------------------------[Commencer l'exploration]--------------------------------------#
while h:
    d, s = heapq.heappop(h) #Extraire par ordre croissant de coût
    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))
#--------------------------------------[Répondre]--------------------------------------#
for answer in dp:
    if answer == INF:
        print('INF')
    else:
        print(answer)

Récupérez le tas dans l'ordre croissant. L'algorithme est facile à comprendre 3.6 Dijkstra Algorithm --Single Source Shortest Path --Greedy Method. La réponse sera si vous le déposez dans le code comme expliqué dans cette vidéo.

057. JOI 2008 Qualifying 6 --Ship Trip

Répondre

import heapq

def cal_cost(graph, n, start, end):
    #--------------------------------------[valeur initiale]--------------------------------------#
    dp = [INF] * (n + 1)
    visited = [-1] * (n + 1)
    dp[start] = 0
    h = [(0, start)]
    #--------------------------------------[Commencer l'exploration]--------------------------------------#
    while h:
        _, s = heapq.heappop(h) #s est le début,e est la fin
        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 est le nombre d'îlots, k est le nombre de lignes pour l'entrée suivante
    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)

C'est une version légèrement différente de la question 56, mais c'est fondamentalement la même chose. En particulier, le contenu de `` cal_cost () '' est presque le même, vous pouvez donc le résoudre si vous ne faites attention qu'à recevoir l'entrée.

058. JOI 2016 Qualifying 5 - Zombie Island

Répondre

from collections import deque
import heapq
#--------------------------------------[valeur initiale]--------------------------------------#
INF = float('inf')
N, M, K, S = map(int, input().split()) #N villes, M routes, K dominé par des zombies, villes dangereuses à l'intérieur S de zombies
P, Q = map(int, input().split()) #P yen si non dangereux, Q yen si dangereux
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))

#--------------------------------------[Explorez la distance de Zombie Town avec BFS]--------------------------------------#
# zombie_BFS pour trouver des villes dangereuses dans S des villes
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_Record comme ensemble pour les villes dangereuses dans S des villes
cost_Q = set()
for i in range(1, N+1):
    if visited[i] <= S:
        cost_Q.add(i)

#--------------------------------------[Recherchez la distance la plus courte avec heapq]]--------------------------------------#
#Tourner le tas
dp = [INF] * (N+1)
visited2 = [-1] * (N+1)
dp[1] = 0
h = [(0, 1)]
answer = 0
while h:
    cost, s = heapq.heappop(h) #s est le début,e est la fin
    if visited2[s] == 1:
        continue
    if s in zombie_towns: #Je ne vais pas dans les villes avec des zombies
        continue
    visited2[s] = 1
    targets = graph[s]

    for target in targets:
        _, e = target

        if e in cost_Q: #  zombie_Q pour les villes dangereuses à l'intérieur de S des villes,A part ça, 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: #Quand la destination sort, arrête-toi là
            answer = dp[s] #La réponse est le coût enregistré juste avant la destination
            break
    if answer != 0:
        break

print(answer)

La mise en œuvre est lourde. Cependant, si vous décomposez ce que vous faites, il est facile à comprendre car il s'agit d'une combinaison des problèmes que vous avez résolus jusqu'à présent. Les problèmes peuvent être globalement divisés en deux: «trouver la distance de la ville zombie» et «trouver le chemin à coût minimum».

Pour "trouver la distance de la ville zombie", utilisez BFS '' pour trouver la distance la plus courte du zombie. Pour "trouver le chemin le moins coûteux", vous pouvez utiliser la méthode Dyxtra avec `heapq```.

059. JOI 2014 Qualifying 5-Taxi

Réponse (TLE (MLE pour pypy))

from collections import deque
import heapq

#------------------[Trouvez la distance de chaque point à chaque destination avec BFS]----------------------#
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__":
    #------------------[contribution]----------------------#
    INF = float('inf')

    N, K = map(int, input().split()) #N villes, K routes
    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)

    #------------------[Reconstruire le graphique]]----------------------#
    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)) #Ajouter au graphique uniquement la partie qui peut aller dans le nombre de fois limite
    
    #------------------[Distance la plus courte avec 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])

Avec le code ci-dessus, 2 cas sur 5 seront TLE ''. Si vous soumettez avec pypy```, un seul des cinq cas sera MLE```.

La grande idée est similaire au problème 58, où vous faites `` BFS '', puis la méthode Dyxtra.

Lorsque vous rédigez une politique,

1. À partir de toutes les villes, calculez le nombre de mains que vous pouvez aller dans chaque ville en vous basant sur `graph``` avec` `bfs```
2. Mettez cette liste d'étapes dans ```end_list` ``
3. Créez un `graph2``` en utilisant` `ʻend_list et le count``` enregistrant la valeur d'entrée `R```
4. Si vous pouvez créer `` `graph2```, tout ce que vous avez à faire est de faire la méthode Dyxtra.

est.

Le `graphe``` donné dans l'énoncé du problème est utilisé pour` `bfs``` Le graph2 '' reconstruit est utilisé dans la méthode Dyxtra, Est-ce là la partie intéressante de ce problème?