战时通信

Grade 100 Open Time Wednesday, 17 June 2020, 10:25 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 10:25 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 10:25 PM
Input file Net.in Output file Net.out

【题目描述】战时通信(NetPOJ 3164

战斗中,指挥官需要将命令通过传输网络下达到各作战单位,命令是单向传输的,不需要下面的作战单位向指挥官报告,现在给出各个作战单位的位置和可以建立连接的作战单位,问最少需要多少通信电缆?

【输入格式】

输入包含多组测试数据,每组测试数据的第一行包含两个整数NN100,表示结点的个数)和MM10 000,表示可以架设有向电缆的结点对的数量)。接下来N行,每行包含两个整数xiyi,表示第i个结点的位置。接下来的M行,每行包含两个整数ij,表示从结点i到结点j可以架设一条有向电缆。指挥官的指挥部在第1个结点。

【输出格式】

每组数据输出一行,包含一个整数,表示至少需要的电缆长度。如果不能建立这样一个通信网,只需要输出“poor snoopy”。

【输入样例】

4 6

0 6

4 6

0 0

7 20

1 2

1 3

2 3

3 4

3 1

3 2

4 3

0 0

1 0

0 1

1 2

1 3

4 1

2 3

【输出样例】

31.19

poor snoopy