【算法分析与设计】我要去西藏

问题描述：
雪域高原，美丽的天路，是许多人向往已久的旅游胜地，更是自驾游爱好者必须前往的目的地。
假设从济南到西藏的路线上共有n个城市1，2，…，n，每个城市都有一个租车公司。你可以在这些城市出租汽车，并在之后的任何一个城市归还汽车。城市i到城市j之间的租金为x(i,j)，1≤i<j≤n。试设计一个算法，计算从济南（城市1）到西藏（城市n）所需的最少租金。
编程任务：
对于给定的城市 i 到城市 j 之间的租金为 x(i,j),1≤i<j≤n，编程计算从城市 1 到城市 n 所需的最少租金。
数据输入：
第1行为n，n<=200），表示有 n个城市。接下来的 n-1 行是 x(i,j),1≤i<j≤n。
结果输出:
计算出的从城市1到城市n所需的最少租金。
样例输入：
3 1 3 5
样例输出：
3
说明
1 3表示： 从城市1到城市2的租金为1 从城市1到城市3的租金为3

代码：

#include <bits/stdc++.h>
 using namespace std;
 #define M 201
 int n , i ,j , k ,a[M][M], ans[M];
 int main()
{
cin >> n;
for( i = 1; i<=n ;i++)
{
    for(j = i+1; j<=n; j++)
    {
        cin >> a[i][j];
    }
}
for(i = n; i>=1; i--)
{
    for(j = i+1; j<=n;j++)
    {
        for(k = i+1; k<j; k++)
        {
            int temp = a[i][k] + a[k][j];
            if(temp < a[i][j])
            {
                a[i][j] = temp;
            }
        }
    }
}
cout <<a[1][n] << endl;
}

转发请注明出处！仅供学习