一道看起来比较纠结的题，但思路很好想：一天一天的递推。看开始没看到“The traveler always starts from city 1”，害得我想复杂了，差点儿把O（n^3）写成O（n^4）。
1 #include<stdio.h>
2 int m,n,f[105][105],cost[105][105];
3 int main()
4 {
5 int i,j,k,max;
6 while(scanf("%d%d",&n,&m)==2)
7 {
8 if(!m && !n) break;
9 for(i = 1; i <= n; i++)
10 for(j = 1; j <= n; j++)
11 scanf("%d",&cost[i][j]);
12 for(i = 1; i <= m; i++)
13 for(j = 1; j <= n; j++)
14 scanf("%d",&f[i][j]);
15 f[0][1] = 0;
16 for(j = 1; j <= n; j++)
17 f[1][j] += f[0][1] - cost[1][j];
18 for(i = 2; i <= m; i++)
19 for(j = 1; j <= n; j++)
20 {
21 max = -1<<20;
22 for(k = 1; k <= n; k++)
23 {
24 if(f[i-1][k] - cost[k][j] > max)
25 max = f[i-1][k] - cost[k][j];
26 }
27 f[i][j] += max;
28 }
29 max = 0;
30 for(j = 1; j <= n; j++)
31 if(f[m][j] > max) max = f[m][j];
32 printf("%d\n",max);
33 }
34 return 0;
35 }