Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "056 --059 Shortest Path Problem: Dijkstra's Algorithm".

2. Summary

I understood the Dijkstra method and the Floyd-Warshall method by watching the channel of Abdul Bari on YouTube. It was very easy to understand, and I solved the problem after watching the video and understanding the algorithm, so I was able to proceed smoothly.

3. Main story

056 --059 Shortest path problem: Dijkstra's algorithm

056. GRL_1_A --Single starting point shortest path

Answer

import heapq
#--------------------------------------[Input receipt]--------------------------------------#
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))
#--------------------------------------[initial value]--------------------------------------#
dp = [INF] * V
visited = [-1] * V
dp[r] = 0
h = [(0, r)]
#--------------------------------------[Start exploration]--------------------------------------#
while h:
    d, s = heapq.heappop(h) #Extract in ascending order of cost
    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))
#--------------------------------------[Answer]--------------------------------------#
for answer in dp:
    if answer == INF:
        print('INF')
    else:
        print(answer)

Fetch in the heap in ascending order. The algorithm is easy to understand 3.6 Dijkstra Algorithm --Single Source Shortest Path --Greedy Method. If you drop it in the code as explained in this video, it will be an answer.

057. JOI 2008 Qualifying 6 --Ship Trip

Answer

import heapq

def cal_cost(graph, n, start, end):
    #--------------------------------------[initial value]--------------------------------------#
    dp = [INF] * (n + 1)
    visited = [-1] * (n + 1)
    dp[start] = 0
    h = [(0, start)]
    #--------------------------------------[Start exploration]--------------------------------------#
    while h:
        _, s = heapq.heappop(h) #s is start,e is end
        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 is the number of islands, k is the number of lines for the following input
    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)

It's a slightly different version of question 56, but basically it's the same thing. In particular, the contents of `cal_cost ()` are almost the same, so you can solve it by just receiving the input.

058. JOI 2016 Qualifying 5 --Zombie Island

Answer

from collections import deque
import heapq
#--------------------------------------[initial value]--------------------------------------#
INF = float('inf')
N, M, K, S = map(int, input().split()) #N towns, M roads, K dominated by zombies, dangerous towns within S from zombies
P, Q = map(int, input().split()) #P yen if not dangerous, Q yen if dangerous
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))

#--------------------------------------[Explore the distance from Zombie Town with BFS]--------------------------------------#
# zombie_BFS to find dangerous towns within S from towns
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 as a set for dangerous towns within S from towns
cost_Q = set()
for i in range(1, N+1):
    if visited[i] <= S:
        cost_Q.add(i)

#--------------------------------------[Search for the shortest distance with heapq]]--------------------------------------#
#Turn the heap
dp = [INF] * (N+1)
visited2 = [-1] * (N+1)
dp[1] = 0
h = [(0, 1)]
answer = 0
while h:
    cost, s = heapq.heappop(h) #s is start,e is end
    if visited2[s] == 1:
        continue
    if s in zombie_towns: #Don't go to towns with zombies
        continue
    visited2[s] = 1
    targets = graph[s]

    for target in targets:
        _, e = target

        if e in cost_Q: #  zombie_Q for dangerous towns within S from towns,Other than that, 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: #When the destination comes out, break there
            answer = dp[s] #The answer is the cost recorded just before the destination
            break
    if answer != 0:
        break

print(answer)

The implementation is heavy. However, if you break down what you are doing, it is easy to understand because it is a combination of problems that you have solved so far. The problems can be broadly divided into two: "find the distance from the zombie town" and "find the minimum cost path".

To "find the distance from the zombie town", use `BFS``` to find the shortest distance from the zombies. To "find the lowest cost path", use the Dijkstra method with `heapq```.

059. JOI 2014 Qualifying 5-Taxi

Answer (TLE (MLE for pypy))

from collections import deque
import heapq

#------------------[Find the distance from each point to each destination with 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__":
    #------------------[input]----------------------#
    INF = float('inf')

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

    #------------------[Rebuild graph]]----------------------#
    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)) #Add to graph only the part that can go within the number of times limit
    
    #------------------[Shortest distance with 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])

With the above code, 2 out of 5 cases will be `TLE```. If you submit with ``` pypy```, only one of the five cases will be `MLE```.

The big idea is similar to question 58, doing `` `BFS``` and then Dijkstra's algorithm.

When you write a policy,

1. Starting from all towns, calculate how many hands you can go to each town based on `graph``` with `bfs```
2. Put this list of steps in ```end_list
3. Create a `graph2``` with a end_list and a `counts with the input value `` R recorded.
4. If you can make graph2, all you have to do is Dijkstra's algorithm.

is.

The graph given in the problem statement is used for `bfs```, The reconstructed `graph2``` is used in Dijkstra's algorithm, Is that the interesting part of this problem?