백준 1504. 특정한 최단 경로

tose33 2022. 7. 9. 13:52

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

처음에 방향을 크루스칼 알고리즘으로 잘못 잡아서 꽤나 해맸다.

하다가 생각해보니 크루스칼이 아닌 다익스트라를 사용하는 문제였다.

시작지점에서 두 정점 p1, p2를 거쳐서 도착지점을 가는 방법은 두가지가 있다.

시작지점 -> p1 -> p2 -> 도착지점

시작지점 -> p2 -> p1 -> 도착지점

두 가지중 작은 값을 출력하면 되는데, 만약 끊어진 길이 있는 경우는 걸러줘야 한다.