| 题目名称 | 1505. 奶牛运输 |
|---|---|
| 输入输出 | cowtrans.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 5 |
| 题目来源 |
 cstdio
于2014-01-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：2， 通过率：100% | ||||
 cstdio |
100 | 0.008 s | 0.55 MiB | C++ |
|
cstdio |
100 | 0.010 s | 0.55 MiB | C++ |
| 关于 奶牛运输 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这个题呢……它比较奇怪……奇怪之处在于最短路矩阵就是那个邻接矩阵……
懒得搞评测插件，直接输出路程长度算了 | ||||
【题目描述】
有一个奶牛运输公司，设在农场A中，它有一个用来在七个农场A，B，C，D、E、F、G之间运输奶牛的运输车。七个农场之间的距离由下表给出：
|
|
B |
C |
D |
E |
F |
G |
|
A |
56 |
43 |
71 |
35 |
41 |
36 |
|
B |
0 |
54 |
58 |
36 |
79 |
31 |
|
C |
. |
0 |
30 |
20 |
31 |
58 |
|
D |
. |
. |
0 |
38 |
59 |
75 |
|
E |
. |
. |
. |
0 |
44 |
67 |
|
F |
. |
. |
. |
. |
0 |
72 |
每天早晨，运输公司都要决定运输奶牛的顺序，使得总路程最少。下面是规则：
1：运输车总是从位于农场A的公司总部出发，而且当所有的运输任务完成之后还要返回总部；
2：运输车一次只能运送一头奶牛；
3：每个运输任务是由一对字母给出的，分别代表奶牛将从哪个农场被运向另一个农场。
你的任务是写一个程序，对一组给定的任务，求出一条完成所有任务的最短路线（从农场A出发，最后返回农场A）。
【输入格式】
输入文件的第一行有一个正整数N(N<=12)，表示任务个数
接下来的N行，每行有两个字符ch1,ch2，表示一个将奶牛从ch1运向ch2的任务
【输出格式】
输出一行一个正整数：最短路线的长度。
【样例输入】
5
F C
G B
B D
A E
G A
【样例输出】
368
【提示】
表格中，“.”意味着这个值前面已经出现过，因为道路是双向的。
【来源】
《信息学奥林匹克》杂志1998年1-2期
1995年美国计算机程序设计选拔赛试题
李刚，《动态规划的深入讨论》