问题 26916 --P服务点设置

26916: P服务点设置

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

为了进一步普及九年义务教育,政府要在某乡镇建立P所希望小学,该乡镇共有n个村庄,村庄间的距离已知,请问学校建在哪P个村庄最好?(好坏的标准是学生就近入学,即在来上学的学生中,以最远的学生走的路程为标准。或者说最远的学生与学校的距离尽可能的小。)

输入

输入由若干行组成,第一行有3个整数,n(1≤n≤100)、m(1≤m≤n*n),p;n表示村庄数,m表示村庄间道路数。第2至m+1行是每条路的信息,每行三个整数,为道路的起点、终点和两村庄间距离。(村庄从0开始编号)

输出

P个整数,学校所在村庄编号(如果P个以上村庄都适合建立学校,选择编号小的P个村庄建学校,输出时按编号从小到大输出)。

样例输入

6 8 2
 0 2 10
 0 4 30
 0 5 100
 1 2 5
 2 3 50
 3 5 10
 4 3 20
 4 5 60 

样例输出

0 3 

来源

 

[提交][状态]