lyzqm   4년 전

모든 대학들은 연결되어야 하기때문에 정점1을 시작지점으로 잡고

다익스트라를 돌려서 dist[next]에 저장했습ㄴ다

그 후에 bfs를 돌려서 dist[next] == dist[here]+edge[here][next] 인 지점들에 대해서만 거리를 더했습니다.

모든대학이 연결안된경우도 체크했는데 어디서 틀린걸까요 ? ㅠㅠ

dtc03012   4년 전

저는 최소스패닝트리로 풀었어요

lyzqm   4년 전

감사합니다!

lyzqm   4년 전

혹시 왜 다익스트라 알고리즘으로 안풀리는지 아시나요?

어디 로직이 틀린지 모르겠네요

simm4256   4년 전

최소 스패닝 트리 문제는 최단 경로 알고리즘으로 풀 수 없습니다.

어떤 그래프의 최소 스패닝 트리에서 임의의 두 점 사이의 거리는, 원래 그래프에서 해당 두 점 사이의 최단 경로와 같지 않을 수 있기 때문입니다.


simm4256   4년 전

4 4
M W M W
1 2 1
2 3 1
3 4 1
1 4 2


간단히 예로 들면 이런 반례가 있습니다.

1-2-3-4 와 같이 연결되어야 문제에서 요구하는 최소 스패닝 트리지만 (답은 3)

다익스트라를 돌리면 (1,4)의 최단경로가 2이기 떄문에 4-1-2-3과 같이 연결되서 답이 4로 나옵니다.

lyzqm   4년 전

오 감사합니다.

궁금증이 풀렸네요

댓글을 작성하려면 로그인해야 합니다.