青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Arctic Network

Description

The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.

Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

Input

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).

Output

For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.

Sample Input

1 2 4 0 100 0 300 0 600 150 750 

Sample Output

212.13 

Source


#include<cstdio>
#include
<cstring>
#include
<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;
const int MAXN = 550;
const double inf = 1e250;
int m,n;
double e[MAXN][MAXN],x[MAXN],y[MAXN],ord[MAXN],cost[MAXN];
bool vi[MAXN];
void prim(int s){
    
for(int i=0;i<n;i++){
        vi[i]
=0;cost[i]=e[s][i];
    }
    vi[s]
=1;cost[s]=0.0;ord[0]=0.0;
    
int u=s;
    
for(int i=1;i<n;i++){
        ord[i]
=inf;
        
for(int j=0;j<n;j++)
            
if(!vi[j] && cost[j]<ord[i])
                ord[i]
=cost[u=j];
        vi[u]
=1;
        
for(int j=0;j<n;j++)
            
if(!vi[j] && e[u][j]<cost[j])
                cost[j]
=e[u][j];
    }
    sort(ord,ord
+n);
    printf(
"%.2lf\n",ord[n-m]);
}
int main(){
    
int t;
    scanf(
"%d",&t);
    
while(t--){
        scanf(
"%d%d",&m,&n);
        
for(int i=0;i<n;i++)
            scanf(
"%lf%lf",&x[i],&y[i]);
        
for(int i=0;i<n;i++)
            
for(int j=i+1;j<n;j++)
                e[i][j]
=e[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        prim(
0);
    }
    
return 0;
}

posts - 3, comments - 1, trackbacks - 0, articles - 16

Copyright © lenohoo

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美激情一区二区三区在线视频| 久久久久www| 欧美色大人视频| 亚洲欧美日韩国产一区二区三区 | 亚洲国产日韩欧美一区二区三区| 久久艳片www.17c.com| 久久免费的精品国产v∧| 亚洲黄色精品| 亚洲视频香蕉人妖| 黑人巨大精品欧美一区二区| 亚洲福利国产| 国产精品激情偷乱一区二区∴| 久久精品国产免费| 欧美aaaaaaaa牛牛影院| 亚洲欧美成人一区二区三区| 欧美一区二区久久久| 亚洲日韩成人| 午夜视频在线观看一区| 亚洲人精品午夜| 亚洲男人的天堂在线| 亚洲激情视频在线播放| 亚洲午夜女主播在线直播| 欧美激情欧美激情在线五月| 欧美日韩亚洲一区二区三区在线 | 亚洲欧美日韩国产中文在线| 久久都是精品| 亚洲一区精品电影| 久久这里有精品视频| 午夜激情亚洲| 欧美激情视频一区二区三区不卡| 欧美中文字幕在线观看| 欧美精品91| 欧美成年人视频网站| 国产精品一区=区| 亚洲日本理论电影| 在线观看视频一区| 午夜精品国产更新| 亚洲综合激情| 欧美老女人xx| 亚洲国产黄色| 亚洲第一在线综合网站| 亚洲欧美日韩精品一区二区 | 中文精品视频一区二区在线观看| 开心色5月久久精品| 久久久久久国产精品一区| 国产精品美女主播| 一本色道久久综合亚洲精品高清| 亚洲精品黄色| 美女黄毛**国产精品啪啪| 久久久午夜精品| 国产午夜精品在线| 亚洲男人的天堂在线aⅴ视频| 亚洲欧美韩国| 国产精品福利在线观看| 一区二区久久久久久| 一区二区欧美在线观看| 欧美激情国产高清| 最新69国产成人精品视频免费| 亚洲第一狼人社区| 蜜臀av性久久久久蜜臀aⅴ| 免费久久99精品国产自在现线| 韩国av一区二区三区四区| 香蕉精品999视频一区二区| 欧美一区精品| 韩国av一区二区| 久久先锋资源| 亚洲国产精品久久久久秋霞蜜臀| 亚洲欧洲精品一区二区三区波多野1战4 | 国产亚洲视频在线观看| 亚洲精品午夜精品| 在线视频精品一| 欧美日韩中字| 亚洲免费中文字幕| 久久久久久久一区二区| 在线观看不卡av| 欧美激情综合色综合啪啪| aⅴ色国产欧美| 久久er精品视频| 狠狠色香婷婷久久亚洲精品| 久久久人成影片一区二区三区| 欧美成人激情视频免费观看| 亚洲精品1区2区| 欧美天天在线| 久久国产精品色婷婷| 亚洲国产欧美一区二区三区久久| 国产精品99久久久久久久vr| 国产欧美日韩不卡| 亚洲综合视频一区| 欧美午夜激情在线| 欧美一区二区三区四区在线观看地址| 久久久久亚洲综合| 日韩午夜中文字幕| 国产欧美亚洲一区| 欧美电影资源| 午夜一级在线看亚洲| 亚洲国产成人av| 亚洲综合欧美| 亚洲人www| 国产乱理伦片在线观看夜一区| 久久噜噜亚洲综合| 亚洲午夜激情| 欧美黄色视屏| 欧美在线视频免费播放| 亚洲精品免费看| 国产在线国偷精品产拍免费yy| 欧美成人在线免费视频| 午夜国产欧美理论在线播放| 亚洲片国产一区一级在线观看| 欧美不卡高清| 校园激情久久| 在线视频精品一区| 亚洲成人在线观看视频| 国产精品一区在线观看| 欧美日韩激情小视频| 久久久99久久精品女同性| 99精品国产在热久久下载| 免费久久99精品国产自| 久久国产毛片| 欧美一区二区三区四区在线| 99精品久久免费看蜜臀剧情介绍| 激情五月***国产精品| 国产精品三级久久久久久电影| 欧美精品在线看| 欧美成人精品影院| 久久久久久电影| 欧美一区午夜精品| 午夜精品一区二区三区电影天堂| 99精品视频免费观看视频| 亚洲国产精品久久久久婷婷老年| 久久综合色影院| 久久综合色播五月| 久久精品人人做人人爽| 久久国产精品黑丝| 久久激情五月婷婷| 久久久久99| 欧美日韩另类视频| 欧美国产综合一区二区| 蜜桃av一区| 欧美成人有码| 欧美日韩第一区日日骚| 欧美日本精品| 国产精品v欧美精品∨日韩| 欧美日韩一区二区三区在线观看免| 欧美精品国产精品| 国产精品播放| 国产日本欧美视频| 狠狠久久综合婷婷不卡| 伊人色综合久久天天| 亚洲国产第一| 99人久久精品视频最新地址| 宅男噜噜噜66一区二区| 亚洲视频香蕉人妖| 亚洲午夜影视影院在线观看| 亚洲欧美日韩国产| 久久久久国产精品一区三寸| 久久综合成人精品亚洲另类欧美| 老司机凹凸av亚洲导航| 欧美激情一区二区在线| 国产精品第一页第二页第三页| 国产精品久久久久影院色老大| 国产日韩在线视频| 亚洲国产精品热久久| 一区二区三区视频观看| 欧美在线高清视频| 欧美电影免费观看大全| 一本色道久久88综合亚洲精品ⅰ | 亚洲精品亚洲人成人网| 亚洲一区二区三区影院| 久久精品毛片| 欧美日韩高清免费| 国产综合色在线| 一本色道久久综合亚洲精品婷婷| 亚洲欧美激情诱惑| 欧美顶级艳妇交换群宴| 亚洲一区二区日本| 免费观看成人| 国产日韩欧美一区二区三区四区| 亚洲风情在线资源站| 亚洲影院免费| 亚洲国产你懂的| 亚洲欧美日韩网| 欧美精品一区二区蜜臀亚洲| 国产丝袜美腿一区二区三区| 亚洲欧洲一区二区在线观看| 午夜在线一区二区| 91久久香蕉国产日韩欧美9色 | 亚洲精品一区二区三区福利| 欧美一区二区三区在线观看视频| 欧美精品一区二区蜜臀亚洲| 国产一区二区久久久| 亚洲综合日韩在线| 亚洲国产精品传媒在线观看| 欧美在线精品一区| 国产精品久久久久久久午夜片| 亚洲精品美女在线观看播放| 久久久97精品| 欧美亚洲免费电影| 国产精品久久婷婷六月丁香| 一本色道婷婷久久欧美| 亚洲国产精品精华液2区45|