하나의 무방향 가중치 연결 그래프가 있다고 가정합니다. 그래프에는 n개의 노드가 있으며 1에서 n까지 레이블이 지정됩니다. 시작에서 끝으로의 경로는 [z0, z1, z2, ..., zk]와 같은 노드의 시퀀스입니다. 여기에서 z0은 시작 노드이고 zk는 끝 노드이며 zi와 zi+1 사이에 에지가 있습니다. 여기서 0 <=나는 <=k-1. 경로의 거리는 경로의 가장자리에 있는 가중치 값의 합입니다. dist(x)가 노드 n과 노드 x로부터의 최단 거리를 나타냅니다. 제한된 경로는 0 <=i <=k-1일 때 dist(zi)> dist(zi+1)도 충족하는 특수 경로입니다. 따라서 노드 1에서 노드 n까지 제한된 경로의 수를 찾아야 합니다. 답이 너무 크면 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 다음과 같으면
세 개의 제한된 경로(1,2,5), (1,2,3,5), (1,3,5)가 있기 때문에 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
graph :=주어진 에지 리스트로부터 만들어진 그래프의 인접 리스트
-
경로 :=크기(n+1)이고 0으로 채워진 배열
-
경로[n] :=1
-
dists :=크기(n+1)이고 -1로 채워진 배열
-
q :=대기열, 처음에 (0, n) 삽입
-
q가 비어 있지 않은 동안 수행
-
(dist, node) :=q의 앞 요소 및 q에서 제거
-
dist[node]가 -1과 같지 않으면
-
다음 반복으로 이동
-
-
dist[노드] :=dist
-
각 인접 노드 v와 그래프[노드]의 가중치 w에 대해 수행
-
dist[v]가 -1과 같으면
-
q에 (dist + w, v) 삽입
-
-
그렇지 않으면 dist[v]
-
경로[노드] :=경로[노드] + 경로[v]
-
-
-
노드가 1과 같으면
-
반환 경로[노드] 모드 10^9+7
-
-
-
0 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict from heapq import heappop, heappush def solve(n, edges): graph = defaultdict(dict) for u, v, w in edges: graph[u][v] = w graph[v][u] = w paths = [0] * (n+1) paths[n] = 1 dists = [-1] * (n+1) q = [(0, n)] while q: dist, node = heappop(q) if dists[node] != -1: continue dists[node] = dist for v, w in graph[node].items(): if dists[v] == -1: heappush(q, (dist + w, v)) elif dists[v] < dists[node]: paths[node] += paths[v] if node == 1: return paths[node] % (10**9 + 7) return 0 n = 5 edges = [(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)] print(solve(n, edges))
입력
5,[(1,2,3),(1,3,3),(2,3,1),(1,4,2),(5,2,2),(3,5,1),(5,4,10)]
출력
3