跳至正文
题库4023
#4023

1348. 【例4-9】城市公交网建设问题

查看题目操作

1348. 【例4-9】城市公交网建设问题

题目描述

有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?

输入格式

第一行两个整数 n、e(2≤n≤100,e≥n−1),表示城市数和边数。接下来 e 行,每行 i、j、w,表示城市 i、j 间一条无向道路的造价;1≤i,j≤n,1≤w≤2147483647。输入图连通,允许重边和自环;自环不能用于连接不同城市,同一对城市间可以选造价最低的道路。

输出格式

输出 n−1 行,每行两个城市编号,表示所选的一条输入道路。所选道路必须连接所有城市,总造价最小。若存在多个最优方案,输出任意一个;道路的方向和输出顺序不限,不得输出额外内容。
5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8
1  2
2  3
3  4
3  5

来源

一本通在线评测 ybtbas-1348