오늘 뭐했지

https://www.acmicpc.net/problem/31230

A도시와 B도시를 잇는 모든 최단경로상의 정점을 구하는 문제입니다.

가중치가 있는 그래프에서 최단경로를 찾아야 하는 문제이기 때문에 다익스트라를 써야겠다는건 알 것 같습니다.

처음 문제를 읽고 최단경로상의 정점을 구해야한다는 것만 읽고 역추적을 해야 하나 고민했습니다.

하지만 가능한 최단경로가 여러가지가 될 수 있고 그 모든 것이 정답이 될 수 있습니다.

단순하게 완전탐색부터 생각하면

A -> B 까지의 최단거리를 X라 하고, 모든 정점(i)에 대해 다익스트라를 돌리며 dist[A] + dist[B] == X이면 i번 정점을 정답에 추가하면 됩니다.

하지만 이렇게 하면 시간복잡도가 O(N^2logM)이 되어 시간초과입니다.

어떤 정점 i에서 A까지의 최단거리와 B까지의 최단거리의 합이 A부터 B까지의 최단거리가 되어야 하는 i들이 궁금한건데,

이것은 정점 A에서 i까지의 최단거리와 B에서 i까지의 최단거리의 합과 동일합니다.

따라서 A에서 다익스트라를 돌려서 나온 거리 배열을 dist_a라 하고,

B에서 다익스트라를 돌려 나온 거리 배열을 dist_b라고 했을때,

모든 1 ~ N번 정점에 대해

dist_a[i] + dist_b[i] == dist_a[B] 인 i들이 정답일 것입니다.

다익스트라 두 번후에 모든 정점에대해 확인하는 것만 하면 되니 시간복잡도가 O(NlogM)으로 줄어 시간 내에 통과 가능합니다.