[TOP] ### L3-2. 垃圾箱分布 時間限制 200 ms 內存限制 65536 kB 代碼長度限制 8000 B 判題程序 Standard 作者 陳越 大家倒垃圾的時候，都希望垃圾箱距離自己比較近，但是誰都不愿意守著垃圾箱住。所以垃圾箱的位置必須選在到所有居民點的最短距離最長的地方，同時還要保證每個居民點都在距離它一個不太遠的范圍內。 現給定一個居民區的地圖，以及若干垃圾箱的候選地點，請你推薦最合適的地點。如果解不唯一，則輸出到所有居民點的平均距離最短的那個解。如果這樣的解還是不唯一，則輸出編號最小的地點。 輸入格式： 輸入第一行給出4個正整數：N（<= 103）是居民點的個數；M（<= 10）是垃圾箱候選地點的個數；K（<= 104）是居民點和垃圾箱候選地點之間的道路的條數；DS是居民點與垃圾箱之間不能超過的最大距離。所有的居民點從1到N編號，所有的垃圾箱候選地點從G1到GM編號。 隨后K行，每行按下列格式描述一條道路： P1 P2 Dist 其中P1和P2是道路兩端點的編號，端點可以是居民點，也可以是垃圾箱候選點。Dist是道路的長度，是一個正整數。 輸出格式： 首先在第一行輸出最佳候選地點的編號。然后在第二行輸出該地點到所有居民點的最小距離和平均距離。數字間以空格分隔，保留小數點后1位。如果解不存在，則輸出“No Solution”。 輸入樣例1： 4 3 11 5 1 2 2 1 4 2 1 G1 4 1 G2 3 2 3 2 2 G2 1 3 4 2 3 G3 2 4 G1 3 G2 G1 1 G3 G2 2 輸出樣例1： G1 2.0 3.3 輸入樣例2： 2 1 2 10 1 G1 9 2 G1 20 輸出樣例2： No Solution