첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 100,000이 주어진다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 길이 C(0 < C ≤ 10,000)인 간선으로 연결되어 있다는 의미이다. 두 정점은 최대 한 개의 간선으로만 연결될 수 있다. 간선은 방향성이 없다.
출력
첫째 줄에 답을 출력한다. 답은 2147483647을 넘지 않는다.
입력 예시
4 4
1 3 1
3 2 2
1 4 2
2 4 1
출력 예시
2
풀이
이동할 때 T에 가까워지는지의 여부를 체크해보려면, 각 정점에서 T와의 거리를 알 수 있어야 한다. 간선 및 정점의 개수를 고려할 때 O(ElogV)의 시간복잡도를 갖는 다익스트라 알고리즘을 사용해보자.
이렇게 정점에서 T까지의 거리를 모두 알 수 있다면, 다음은 합리적인 이동경로를 탐색해야 한다. 이 역시 완전탐색으로는 비효율적인 시간 소모를 야기하게 된다. 따라서 DP를 한 움큼 가미해보자. 이미 방문한 정점에서의 합리적인 이동경로 갯수가 있다면, 이 이동경로 갯수를 불러와 사용할 수 있다.
풀이 코드
from collections import defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
MAX = float('inf')
N, M = map(int, input().split())
edge_list = defaultdict(list)
for _ in range(M) :
a, b, dist = map(int, input().split())
edge_list[a-1].append((b-1, dist))
edge_list[b-1].append((a-1, dist))
dp = [-1]*N
dist_list = [MAX]*N
dist_list[1] = 0
q = [ (0, 1) ]
def dfs(node) :
if node == 1 :
return 1
if dp[node] > -1 :
return dp[node]
result = 0
for nxt, _ in edge_list[node] :
if dist_list[node] > dist_list[nxt] :
result += dfs(nxt)
dp[node] = result
return dp[node]
while q :
dist, node = heappop(q)
if dist_list[node] < dist :
continue
for nxt, nxt_dist in edge_list[node] :
if dist_list[nxt] > dist + nxt_dist :
dist_list[nxt] = dist + nxt_dist
heappush(q, (dist + nxt_dist, nxt))
if dist_list[0] == MAX :
print(0)
else :
print(dfs(0))