BOJ 백준온라인져지 1916 최소비용 구하기 풀이

다익스트라 알고리즘을 2번 돌린다.

while loop에서 모두 처음에

t에 X를 넣어주고, i -> t, t -> i 의 minimum distance를 구한다.

간선이 있으면, 값을 체크해서 넣어주고

visited[t] = true로 만들고 다음 반복으로 간다.

그 다음부터는 더 짧은 거리가 있다면, 업데이트 해준다.

결론적으로 구하는 방법은 i -> t 갈 때, t -> i 갈때 를 구해서 더해준다.

i -> 와 t -> 의 경로는 다를 수 있다.