[BOJ] 2176 - 합리적인 이동경로 (Python)

 

 

아이디어

 

다익스트라로 2번 정점까지의 최단 거리를 구한 후, 트리에서의 동적 계획법으로 경로의 수를 구한다.

 

 

풀이

 

import sys
from heapq import heappush, heappop

sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

INF = int(1e7)

def solution():

    def dfs(u):
        if dp[u]:
            return dp[u]
        if u == 2:
            return 1
        for v, c in graph[u]:
            if D[v] < D[u]:
                dp[u] += dfs(v)
        return dp[u]

    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        graph[A].append((B, C))
        graph[B].append((A, C))
    D = [INF]*(N+1)
    D[2] = 0
    heap = [(0, 2)]
    while heap:
        c, u = heappop(heap)
        for v, _c in graph[u]:
            if c+_c < D[v]:
                D[v] = c+_c
                heappush(heap, (c+_c, v))
    dp = [0]*(N+1)
    dfs(1)
    print(dp[1])

solution()