1261：【例9.5】城市交通路网（基础动态规划）

【题目描述】 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

如图：求v1到v10的最短路径长度及最短路径。

【输入】 第一行为城市的数量N;

后面是N*N的表示两个城市间费用组成的矩阵。

【输出】 A->E的最省费用。

【输入样例】 10 0 2 5 1 0 0 0 0 0 0 0 0 0 0 12 14 0 0 0 0 0 0 0 0 6 10 4 0 0 0 0 0 0 0 13 12 11 0 0 0 0 0 0 0 0 0 0 3 9 0 0 0 0 0 0 0 0 6 5 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0

【输出样例】 minlong=19 1 3 5 8 10

---

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int> > grid(105, vector<int>(105));
vector<int> d(105, INT_MAX);
vector<int> nextPos(105);

void solve()
{
    d[n] = 0;
    //逆推查找最短路径
    for (int i = n - 1; i >= 1; --i) {
        for (int j = i + 1; j <= n; ++j) {
            if (grid[i][j] > 0 && d[j] != INT_MAX && d[i] > grid[i][j] + d[j]) {
                d[i] = grid[i][j] + d[j];
                nextPos[i] = j;
            }
        }
    }

    cout << "minlong=" << d[1] << endl;
    int city = 1;
    while (city) {
        cout << city << ' ';
        city = nextPos[city];
    }
    cout << endl;
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> grid[i][j];
        }
    }
    solve();

    return 0;
}

用数组d[i]代表第i个城市到城市n的最短距离，显然d[n] = 0。初始化d[i] = INT_MAX，状态转移方程是： $$ d[i] = \min(grid[i][j] + d[j]) $$ 这里grid[i][j]大于0代表城市i和城市j相连，如果d[j]不为INT_MAX，说明从j到城市n是存在连通路径的。思路其实就是，既然正向去寻找从1到n的最短路径不好找，那么就从终点逆推去寻找路径。