알고리즘/문제풀이 - 백준

백준 9370 미확인 도착지

문제 : https://www.acmicpc.net/problem/9370 서론 최단경로 문제이므로 다익스트라로 접근했다. 이 문제는 풀이 아이디어가 두개다 하나는 다익스트라를 두번 사용하는 방법이고 또 다른 하나는 다익스트라를 세번 사용하는 방법이다. 테스트케이스가 여러개라서 매번 간선을 초기화해줘야하는데 초기화하는 부등호를 H->T S->H->G->T 두가지다. 즉 목적지 후보 T에 대해 S->T까지의 최단거리 = S->G까지의 최단거리 + G->H까지의 최단거리 + H->T까지의 최단거리 가 성립하거나 S->T까지의 최단거리 = S->H까지의 최단거리 + H->G까지의 최단거리 + G->T까지의 최단거리 가 성립하면 간선 GH를 포함한 최단경로를 통해 도착한 것이므로 출력하면 된다. 그리고 위의 조..

2019. 8. 29. 22:29