안녕하세요,
재재입니다.
BOJ 14554 The Other Way 문제 풀이입니다.
BOJ 14554 The Other Way
(1) 문제 설명
분류 : graph, dijkstra
출처 : https://www.acmicpc.net/problem/14554
(10만 이하) N개의 마을이 있습니다.
(30만 이하) M개의 도로가 주어지는데, 양방향입니다.
시작 점과 끝 점이 주어졌을 때, 최단 거리로 끝
점까지 가는 경우의 수를 100,000,009로 나눈 나머지를 구하면 됩니다.
(2) 풀이 도출
시작점부터 끝점까지 가는 최단 거리를 구하는 과정에서,
경우의 수를 들고 있을 수 있습니다.
최단 거리가 갱신 될 때 마다 경우의 수가 초기화가 되고,
해당 지점에 동일한 비용으로 도달하는 경우, 경우의 수를 더해야 합니다.
이게 가능한 이유는,
dijkstra algorithm을 사용하면 항상 작은 코스트의,
노드부터 방문하는게 보장 되기 때문에 가능합니다.
이때, 전체 시간복잡도는 $$ O(n logn) $$ 입니다.
BOJ 14554 The Other Way