codeground : 캠퍼스와 도로(1) [SCPC 2015

Problem Solving

1ssrek 2016. 10. 1. 21:43

codeground : 캠퍼스와 도로(1) [SCPC 2015 - 1차 예선]

SW역량테스트를 맞아 codeground문제들도 써보려고 한다.

그 첫번째 문제..

이 문제는 v번의 다익스트라 알고리즘으로 떠오르는 아이디어 그대로 해결할 수있다.

시간복잡도는 v*(v+e)log(v+e)가 되어 시간안에 충분히 해결할 수 있을 듯 하다.

다만, 방문하는 도시까지의 거리가 같을 때가 문제 ㅜㅜ...

힙에 push하기 전에 방문노드를 체크해주면 왜안되는지 모르겠다. 아직 밝혀내지 못했음...

해결한 방법은, 코드가 조금 길어지긴하지만 스타팅 지점인 v번째 도시에 대해 다익스트라 알고리즘으로 모든 경로까지의 최단거리를 구한 후, 각 edge가 v번째 도시의 최단경로를 만드는 데 참여하는지 확인하는 방법으로 해결하였다.