连线数由连线矩阵 conn 给出。元件 i 和元件 j 之间的连线数为 conn(i,j)。如果将元件 i 安装
在线路板上位置 r 处，而将元件 j 安装在线路板上位置 s 处，则元件 i 和元件 j 之间的距离
为 dist(r,s)。确定了所给的 n 个元件的安装位置，就确定了一个布线方案。与此布线方案相
应的布线成本为
。试设计一个算法找出所给 n 个元件的布线成本最小的布线方案。«算法设计：
设计一个算法，对于给定的 n 个元件，计算最佳布线方案，使布线费用达到最小。
1389: 算法实现题 5-16 布线问题（习题 5-21）
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $15$ | 正确数量 | $3$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 回溯 |
Description
假设要将一组元件安装在一块线路板上，为此需要设计一个线路板布线方案。各元件的
连线数由连线矩阵 conn 给出。元件 i 和元件 j 之间的连线数为 conn(i,j)。如果将元件 i 安装
在线路板上位置 r 处，而将元件 j 安装在线路板上位置 s 处，则元件 i 和元件 j 之间的距离
为 dist(r,s)。确定了所给的 n 个元件的安装位置，就确定了一个布线方案。与此布线方案相
应的布线成本为 。试设计一个算法找出所给 n 个元件的布线成本最小的布线方案。
«算法设计：
设计一个算法，对于给定的 n 个元件，计算最佳布线方案，使布线费用达到最小。
连线数由连线矩阵 conn 给出。元件 i 和元件 j 之间的连线数为 conn(i,j)。如果将元件 i 安装
在线路板上位置 r 处，而将元件 j 安装在线路板上位置 s 处，则元件 i 和元件 j 之间的距离
为 dist(r,s)。确定了所给的 n 个元件的安装位置，就确定了一个布线方案。与此布线方案相
应的布线成本为
。试设计一个算法找出所给 n 个元件的布线成本最小的布线方案。«算法设计：
设计一个算法，对于给定的 n 个元件，计算最佳布线方案，使布线费用达到最小。
Sample Input复制
3
2 3
3
Sample Output复制
10
1 3 2
推荐代码 查看1389 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$228 $ms] | LJHWD | 1102096 | 2024-05-22 22:19:43 |
| 内存最少[$2024 $KB] | WHeng | 929139 | 2022-12-08 16:04:38 |
| 第一AC | WHeng | 929139 | 2022-12-08 16:04:38 |
| 第一挑战 | czc | 925692 | 2022-12-02 17:24:22 |
赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|