문제 링크
https://www.acmicpc.net/problem/9370
문제 해결
1. 최단 거리를 구하는 문제.
2. 시작점과 도착점이 될 수 있는 후보 점들이 주어진다. 도착점이 되기 위해선, 반드시 g와 h 사이의 간선을 지나야한다.
3. dist1[i] = 시작점으로부터 모든 점까지의 최단 거리.
dist2[i] = dist1[g]와 dist1[h] 중 가까운 점 g 또는 h로부터 모든 점까지의 최단 거리
4. 도착점이 될 수 있는 점 t가 있을 때, dist1[t] == dist1[min(dist1[g],dist1[h])인 점] + dist2[t] 이 되는 t를 오름차순으로 출력
주의할 점 || 생각해볼 점
1. testcase마다 graph를 초기화시키는 과정에서 실수가 있었다. 항상 조심해야한다.
참고
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > 그래프_최단 거리' 카테고리의 다른 글
BOJ 16236 - 아기 상어 (0) | 2018.03.14 |
---|---|
BOJ 4179 - 불! (3) | 2017.11.03 |
BOJ 2206 - 벽 부수고 이동하기 (0) | 2017.10.19 |