思路与算法

反向考虑每个城市到N的最短费用。把矩阵列当作反图出边，从N做朴素Dijkstra，得到d[u]。若d[1]无穷则输出minlong=-1。否则从1开始，按编号升序选第一个满足w[u][v]>0且w[u][v]+d[v]=d[u]的v，依次输出直到N。

正确性说明

边权为正，反图Dijkstra每次选取的最小未确定距离不可能再被尚未确定顶点改善，因此d是各点到N的最短费用。路径构造只选距离相容边，所以始终能保持最短总费用；正权使d严格下降，不会产生循环。任意最短路径的下一点都必须满足同一等式，选择其中最小编号使最早不同位置最小，逐步归纳得到字典序最小最短路径。

复杂度

矩阵读入和初始化O(N²)，朴素Dijkstra O(N²)，路径扫描最多O(N²)，总时间O(N²)，空间O(N²)。费用及距离用64位整数。

易错点

矩阵0表示无边，不能当作免费道路。图是有向的，反向松弛应读取w[v][u]。N=1费用0且路径为1。不可达时不构造路径；多解必须执行编号升序的相容边选择。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<vector<ll>> a(n, vector<ll>(n));
    for (auto &r : a)
        for (auto &x : r)
            cin >> x;
    const ll INF = 4e18;
    vector<ll> d(n, INF);
    vector<bool> done(n);
    d[n - 1] = 0;
    for (int k = 0; k < n; ++k) {
        int u = -1;
        for (int i = 0; i < n; ++i)
            if (!done[i] && (u < 0 || d[i] < d[u]))
                u = i;
        if (u < 0 || d[u] == INF)
            break;
        done[u] = true;
        for (int v = 0; v < n; ++v)
            if (a[v][u] > 0)
                d[v] = min(d[v], a[v][u] + d[u]);
    }
    if (d[0] == INF) {
        cout << "minlong=-1\n";
        return 0;
    }
    cout << "minlong=" << d[0] << "\n";
    int u = 0;
    cout << 1;
    while (u != n - 1) {
        for (int v = 0; v < n; ++v)
            if (a[u][v] > 0 && d[v] != INF && a[u][v] + d[v] == d[u]) {
                cout << ' ' << v + 1;
                u = v;
                break;
            }
    }
    cout << "\n";
}