[백준] 1504번 특정한 최단 경로 c++

흠 너무 어렵게 생각해서 못 풀고 있었다. 일단 1 -> v1 -> v2 -> N 과 1 -> v2 -> v1 -> N의 경로를 구해서 둘 중 더 짧은 걸 구해주면 된다. 이때 경로의 총합이 MAX보다 크면 경로가 없다는 의미기이게 -1 출력 근데 여기서 당연히 1 -> v1 -> v2 -> N가 최단 경로인데 다른 곳을 거쳐 가는 게 최다 경로면 어떡하지 이 생각을 했다. 생각해 보면 다른 곳 거쳐서 v1 v2 지나면 그만큼 더 가니 최단 경로가 아니다. 즉 2가지 경우만 구해주면 된다. 다 엑스트라를 3번 돌렸다. 1번 정점을 기준으로 다익스트라를 돌리면 1 -> v1, 1 -> v2 구할 수 있다. v1 정점을 기준으로 다익스트라를 돌리면 v1 -> v2,..........

원문링크 : [백준] 1504번 특정한 최단 경로 c++