奶牛运输

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file cowtrans.in Output file cowtrans.out

【题目描述】

有一个奶牛运输公司,设在农场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年美国计算机程序设计选拔赛试题

李刚,《动态规划的深入讨论》