import sys
input = sys.stdin.readline
from heapq import *
def Dijkstra():
DP = [1e9]*N
hq = [(0,1)]
while hq:
w,now = heappop(hq)
if DP[now] <= w:
continue
DP[now] = w
for next,w1 in graph[now]:
heappush(hq,(w+w1,next))
return DP
def DFS(now):
for next,w in graph[now]:
if Dij[now] <= Dij[next]:
continue
if not DP[next]:
DFS(next)
DP[now] += DP[next]
N,M = map(int,input().split())
graph = [[] for i in range(N)]
for _ in range(M):
a,b,c = map(int,input().split())
graph[a-1].append((b-1,c))
graph[b-1].append((a-1,c))
Dij = Dijkstra()
DP = [0]*N; DP[1] = 1
DFS(0)
print(DP[0])
간단한 다 익스트라 + DFS + DP 문제
알고리즘은 여러개 쓰이지만 풀이는 매우 간단하다.
설명하면,
1. 다 익스트라로 2번 노드에서 모든 노드까지의 최단거리를 측정한다.
2. DFS + DP로 최단거리가 작아지는 경우에만 탐색을 하며 경우의 수를 센다.
골드 1 문제 정도는 이제 대부분 가볍게 풀 수 있는 수준이 된 것 같다. 앞으로도 열심히 해야겠다.
오늘의 교훈) 플래티넘도 가볍게 풀 수 있을 때까지 화이팅