1507 궁금한 민호

각 정점간의 최단 거리가 주어졌을 때, 다리를 몇개 놓아야 하는지 묻는 문제다

 

먼저 우선순위 큐에 edge 정보를 넣어, 거리가 짧은 순서대로 pop을 한 다음,

만일, 두 노드 중 하나라도 방문하지 않았다면 다리를 설치해야한다. 그리고 모두 방문했다면 모든 경유지를 탐색해보면서 입력에서 제공한 최단경로와 맞다면 넘어가고, 아니라면 다리를 설치하도록 한다

 

불가능한 경우는 헷갈렸는데, 입력이 잘못된 형태다. 즉 다리 설치를 조사해가면서 입력에서 제공한 경로보다 짧은 경우가 나온다면 그 경우는 잘못된 것이다

 

문제: https://www.acmicpc.net/problem/1507

https://github.com/surinoel/boj/blob/master/1507.cpp