[Python] boj no. 2176 : 합리적인 이동경로

Problem

https://www.acmicpc.net/problem/2176

Idea

합리적인 이동경로는 정점을 지날 때마다 T까지의 최단 경로 값이 줄어드는 경로를 말한다.

T를 시작점으로 다익스트라 알고리즘을 이용하여 T부터 각 노드까지의 최단 경로인 dist를 구한다. 이를 통해 T부터 S까지의 합리적인 이동경로를 구한다. T->S의 합리적인 이동경로는 결국 S->T의 합리적인 이동경로와 같기 때문이다.

다익스트라 알고리즘의 최단 경로 갱신 과정에서 현재 노드까지의 최단 경로보다 다음 노드까지의 최단 경로가 더 짧다면 그 노드를 거치는 경로가 있음을 의미한다. 다음 노드까지 도달하는 합리적인 이동경로의 수에 현재 노드까지 도달하는 합리적인 이동경로의 수를 더한다. 이 과정을 반복함으로써, T부터 S까지의 합리적인 이동경로의 수를 구할 수 있다.

Code

import sys
import heapq

input = sys.stdin.readline
   
def dijkstra(start):
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (dist[start], start))

    while heap:
        cd, cn = heapq.heappop(heap)

        if cd > dist[cn]:
            continue

        for weight, nn in edge[cn]:
            if dist[cn] + weight < dist[nn]:
                dist[nn] = dist[cn] + weight
                heapq.heappush(heap, (dist[nn], nn))
                
            if dist[cn] > dist[nn]:
                dp[cn] += dp[nn]

N, M = map(int, input().split())
edge = [[] for _ in range(N+1)]
dist = [sys.maxsize for _ in range(N+1)]
dp = [0 for _ in range(N+1)]
for _ in range(M):
    A, B, C = map(int, input().split())
    edge[A].append((C, B))
    edge[B].append((C, A))

dp[2] = 1
dijkstra(2)
print(dp[1])

Comment