P7176: 丢失的地图

---

【题目描述】

【问题描述】
在世界上的某个山区，有一个由n个村庄组成的部落。这些村庄由一系列道路所连接，道路允许双向行驶。由于地形险恶，修建这些道路的费用很高，因此需要修建最少的道路，并使每个村庄都可以通过一系列道路互相到达。
这些村庄之间的贸易非常重要，因为并非每个村庄都能获得相同的自然资源供应。然而，许多村庄生产相同的资源，因此，了解村庄与其他村庄的相对距离是很有用的，这样他们就可以选择贸易伙伴，以最大限度地降低总体贸易成本。注意，两个村庄a和b之间的距离是连接a和b的最短路径上的各条道路的长度之和。
一个计算每对村庄之间距离的项目正在进行中。这些信息已包含在一张表格中，同时还有一张显示村庄布局和村庄之间道路的地图，你的任务是把表格和地图分发到所有的村庄，以促进村庄经济的发展。
不幸的是，就在你这项任务后不久，一阵风把你手中的地图吹到了乡下。尽管你尽了最大的努力寻找它，但你还是无法找到它。你知道你可以访问所有的村庄来重建地图，然后开始分发地图和表格，但这将花费原来任务的两倍时间，村庄会对你非常不满。你可能会想，也许只根据表格才能重建地图？
【输入】
第一行输入将包含整数n（2≤n≤2500），即该地区的村庄数量。接下来的n行每亩行包含n个整数。第i行第j列是从村庄i到村庄j的距离。所有距离都大于零（除非i=j），小于10000000，并且保证从村庄i至村庄j的距离与从村庄j至村庄i的距离相同。
【输出】
输出n-1行，每行上有两个整数u和v，表明该区域有一条连接村庄u和v的道路。能让所有村庄都能连通且路径最短。
【样本输入1】
4
0 1 1 2
1 0 2 3
1 2 0 3
2 3 3 0
【样本输出1】
1 2
1 3
1 4
【样本输入2】
7
0 2 9 1 4 3 3
2 0 11 1 6 3 3
9 11 0 10 5 12 12
1 1 10 0 5 2 2
4 6 5 5 0 7 7
3 3 12 2 7 0 4
3 3 12 2 7 4 0
【样本输出2】
1 4
1 5
2 4
3 5
4 6
4 7

题目类型~

初级 难度1.9 

咻咻~

提交答案 状态 返回