【题解】城市交通路网

状态定义：dp[i]:从源点s到顶点i的最短路径长度。
初始状态：目标为求最小值，dp数组各元素初始化为无穷大。起点到起点的距离为0：dp[s]=0，

用邻接矩阵保存边，edge[i][j]表示顶点i到顶点j的距离
预先确定题中给定的顶点序列是图中各定点的拓扑排序序列。
设数组dp，dp[i]表示从源点s到顶点i的最短路径的长度，初值为无穷大，dp[s] = 0;
外层i从1遍历到n，层j从1遍历到i-1，运行状态转移方程：
dp[i] = min{dp[j]+edge[j][i]}
用path数组记录路径，path[i]表示最短路径中i的前一个顶点。输出时用递归或栈来倒序输出。

#include <bits/stdc++.h>
using namespace std;
#define N 15
int edge[N][N], dp[N];//dp[i]:从顶点1到顶点i的最短路径长度 
int path[N];//path[i]:最短路径中i的前一个顶点
void showPath(int i)
{
    if(i == 0)//源点的上一个顶点是0 
        return;
    showPath(path[i]);
    cout << i << ' ';
} 
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            cin >> edge[i][j];
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < i; ++j)
        {
            if(edge[j][i] && dp[i] > dp[j]+edge[j][i])
            {
                dp[i] = dp[j]+edge[j][i];
                path[i] = j;
            }
        }
    cout << "minlong=" << dp[n] << endl;
    showPath(n);
    return 0; 
}