[백준] 2176번 합리적인 이동경로 파이썬

문제

그래프의 한 정점 S에서 다른 한 정점 T로 이동하려 한다. 이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 이동경로라 한다. 물론 이러한 경로는 최단경로가 아닐 수도 있다.

그래프가 주어졌을 때 가능한 합리적인 이동경로의 개수를 구하는 프로그램을 작성하시오. S = 1, T = 2 인 경우로 한다.

입력

첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 100,000이 주어진다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 길이 C(0 < C ≤ 10,000)인 간선으로 연결되어 있다는 의미이다. 두 정점은 최대 한 개의 간선으로만 연결될 수 있다. 간선은 방향성이 없다.

출력

첫째 줄에 답을 출력한다. 답은 2147483647을 넘지 않는다.

예제 입력 1

4 4
1 3 1
3 2 2
1 4 2
2 4 1

예제 출력 1

2

제출 답안

• 여기서는 최단경로를 시작이 아니라 끝에서 거슬러 올라가며 dp를 같이 업데이트 한다.

'''
1. 아이디어
- 2에 대한 count 리스트를 만들어서 횟수 증가 시키기
2. 시간 복잡도
ElogV
- E : 100,000
- logV : 1,000 ~= 10
= 1,000,000 < 2억
3. 변수
- edge [][]
- dist []
- dp []
'''

import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize

n , m = map(int, input().split())
s, t = 1, 2
edge = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, w = map(int, input().split())
    edge[a].append((w, b))
    edge[b].append((w, a))

dist = [INF] * (n+1)
dp = [0] * (n+1)

dist[t] = 0
dp[t] = 1
heap = [(0, t)]
while heap:
    ew, ev  = heapq.heappop(heap)
    if dist[ev] < ew:continue
    for nw, nv in edge[ev]:
        if nw + ew < dist[nv]:
            dist[nv] = ew + nw
            heapq.heappush(heap, (ew + nw, nv))
        if dist[nv] < ew :
            dp[ev] += dp[nv]

print(dp[s])