cokcjswo   7년 전

map[i][]는 i를 짓기 위해 j가 필요하면 true가 되게했습니다.


즉, i짓는데 l이 필요하고 l짓는데 j가 필요하면 i짓는데도 j가 필요하게 끔해서 (플루이드 와샬)

다 처리후

최종적으로 i 건물에 연결된 건물들의 설치 비용을 모두 더해주는게 (i 건물 자신도 포함) i를 짓는 최소비용이라고 생각했는데요


왜 틀린걸까요?


ㅠㅠ

sksdong1   7년 전

5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 2 -1


이거 마지막이 27나오시는데 답 23입니다.

그려보면 1 -> 2, 1->4 온 이후에 

2-> 5, 4->5를 따질 때 오래걸리는 부분만 따지면 되는데 모든 시간을 다 더하네요

cokcjswo   7년 전

ㅇㅏ 동시에 여러 건물을 지을 수 있나보군요 !! 감사합니다 !!

cokcjswo   7년 전

문제를 잘못이해했을 때는 거의 이때까지 본 문제중 제일 어려운 문제였는데, 설명해주신거 듣고 곰곰히 생각해보니 5분 안에 풀었네요... 감사합니다 !!!!!!!!

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