首页 > 试题广场 >

友好城市

[编程题]友好城市
  • 热度指数：996 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
某国家一共有 n 座城市，有的城市与城市与城市之间有路相连，所有的路都是无向的， n 个城市可以通过道理相互达到，其中 2k 座城市是重要城市，国王希望把这 2k 座城市两两配对，形成 k 对友好城市。
友好城市之间常常需要进行交流，因此国王希望友好城市之间的距离不要太长，于是他定义两个城市 u，v 配对的代价为 u，v 之间最短路的长度，2k 座城市配对的总代价为 k 对城市配对的代价和。
国王想知道配对的最小代价。
数据范围： ， 或 ， ，

输入描述:
第一行输入一个数 n ，表示城市个数。
接下来输入一个 n*n 的邻接矩阵 A ， A[i][j] 表示城市 i 和 城市 j 之间边的长度，如果 A[i][j] = -1，表示 i 和 j 之间没有直接相连的边，输入保证 A[i][j] = A[j][i] ，A[i][i] = -1 ，且 n 个城市相互连通。
最后输入一个数 k ，接下来一行 2k 个数，这 2k 个重要城市的编号


输出描述:
输出一个数，最小匹配代价
示例1

输入

4
-1 2 -1 10
2 -1 3 -1
-1 3 -1 1
10 -1 1 -1
2
1 2 3 4

输出

3
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

图 dfs
难度：
0条回答 2899浏览

热门推荐

通过挑战的用户

查看代码

相关试题

友好城市

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号