OI题库

【题目描述】

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

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