백준 2176 썸네일형 리스트형 [Python][백준 2176][다익스트라,DP] 합리적인 이동경로 - 컴도리돌이 2176번: 합리적인 이동경로 첫째 줄에 정점의 개수 N(1 < N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 100,000이 주어진다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 길이 www.acmicpc.net 풀이 과정 DP를 최단 경로를 탐색하기 위하여 사용된다. dp의 i번째 인덱스는 출발하는 합리적인 이동경로의 수를 의미하며, 도착점 2번 노드부터 탐색을 시작한다. 각 정점까지의 최단경로를 갱신하는 과정에서 현재 노드까지 최단 경로의 길이가 다음 노드까지 최단 경로의 길이보다 짧을 경우, 다음 노드와 현재 노드 사이에 합리적인 이동 경로가 존재한다는 뜻이다. 풀이 과정 import sys,heapq; input =.. 더보기 이전 1 다음
