문제풀이

다익스트라를 이용해 특정 간선을 포함하는 최단거리를 구하는 문제이다.
최단거리가 특정 간선을 포함하는지 판단하는게 중요한 문제이다.
처음에 생각했던 방법은 아래와 같다.

1. 다익스트라로 최단거리를 구한다.
2. 최단 거리를 구하는 과정에서 최단경로도 함께 구한다.
3. 해당 경로를 거꾸로 돌아가면서 특정간선을 포함하는지 확인한다.

위 방법은 반례가 있다. 최단거리의 경로가 2가지 이상인데 특정간선을 포함하지 않는 최단경로가 있다면 그 방법을 잡아낼 수 없다. 그래서 틀렸다.
두 번째 방법은 아래와 같다.

1. 출발점,특정간선의 정점들을 s,g,h라 할 때 각 정점 3개로 부터 다익을 각각 돌린다.
2. 도착점을 e라고 했을 때 dist(s,e)값은 dist(h,e)+특정간선(g,h)의 거리+dist(g,s) 혹은 dist(g,e)+특정간선(g,h)의 거리+dist(h,s)와 같아야 한다.
3. 위 조건을 만족하면 특정간선(g,h)를 포함하는 최단경로 인것이다.

그림을 그려본다면 쉽게 이해가 될 것 이다.

코드

solution

문제링크

boj/9370