[BOJ]9370번: 미확인 도착지

www.acmicpc.net/problem/9370

---

문제를 잘 읽어보셔야 합니다.

 

출발지 -> 후보지로 가는 최단 경로 중에 주어진 경로 g,h가 포함된 후보지를 고르는 문제입니다.

 

저는 문제 잘못 읽어서 가장 짧은 후보지 고르는 줄 알고 헤맸습니다.

 

출발지 s, 후보지 c, 주어진 경로 g,h라고 한다면

 

1. 출발지에서 다익스트라를 돌립니다.

2. 주어진 경로 g, h에서 다익스트라를 돌립니다.

 

그리고 두 조건 중 하나를 만족하면 정답입니다.

1. 출발지 → 후보지 거리 == 출발지 → g 거리 + g 거리 → h 거리 + h 거리 →후보지 거리

2. 출발지 → 후보지 거리 == 출발지 → h 거리 + h 거리 → g 거리 + g 거리 →후보지 거리

 

정답 후보는 최단 경로에 g,h 경로가 포함되어 있음이 보장되어있기 때문입니다.

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ9370.cc