특정한 정점을 반드시 거쳐야하는 최단 경로를 구하는 다익스트라 응용

1. 문제 1504번: 특정한 최단 경로 (acmicpc.net) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1번부터 n번까지 최단 경로로 이동하고 싶은데, 특정한 정점 v1,v2를 반드시 거쳐서 최단 경로로 가고 싶다면 어떻게 해야할까? 2. 풀이 다익스트라는 어떤 정점에서 나머지 정점까지 도달하는 최단 경로를 제공하는데, 여기 중간에 어떤 정점을 거칠지는 말해주지 않는다... 근데 어떤 정점을 반드시 거쳐가게 할려면 어떻게 해야할까? 생각보다 간단하다 1번..