练习专区

今天的一小步就是明天的一大步

Problem 1900 旅游2.........数构

Accepted: 1 Total Submit: 2
Time Limit: 1000ms Memory Limit: 30720KB

Description

小王要去旅游，他选好旅游城市，标号从1开始，画出一张旅游图，并用邻接矩阵表示。邻接矩阵上的元素a_ij表示，从i城市到j城市的费用。请你算出周游的最小费用（从1开始回到1，每个城市都要遍历）。自己到自己的费用为0。2城市不直接连通的费用标为E。

Input

有若干个案例，每个案例的第一个数是n（0<n<20），接着是n*n的矩阵。

Output

按样例输出。

Sample Input

5
0 100 100 E 400
100 0 E 200 E
100 E 0 E 300
E 200 E 0 300
400 E 300 300 0

Sample Output

Case 1:1000元

Hint

提交　　　　　返回