어떤 DAG 그래프 G = (V, E)에 대해서, Vertex에 건물을 지을 수 있고 cost는 각각 다르다고 하자.

이 때, 모든 Vertex는 건물을 지은 Vertex에서 출발하여, 도착할 수 있어야 한다.

이 때 건물을 짓는데 든 비용의 평균값 중, 최솟값을 구하시오.


DAG임이 보장되니까, indegree가 0인 Vertex들 cost를 전부 더하고, 

Vertex를 cost에 따라 sorting 한 후 앞에서부터 평균값 비교하면서 순회했는데, 이러면 안되는건가?? 

혹시 어떻게 구해야 할 지 아는사람?