#include <iostream> #include <queue> #include <stack> #include <cstdio> using namespace std; const int INF=0x3f3f3f3f;//无穷大 int n,g[105][105]; int dis[105],pre[105],vis[105]; struct edge { int u,v,d;//边的起点、终点、权值 bool operator < (const edge &a) const { return d>a.d; } }; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>g[i][j]; if(g[i][j]==0) g[i][j]=INF; } priority_queue<edge> q;//优先队列 int temp=1;//当前顶点 int cnt=0;//当前边数 for(int i=1;i<=n;i++) { if(i!=temp) { pre[i]=temp; dis[i]=g[temp][i]; q.push({temp,i,g[temp][i]}); } }//从结点temp开始，此题为从结点1开始 while(!q.empty()) { edge t=q.top(); q.pop(); int v=t.v; if(vis[v]) continue;//已经在已加入点的集合当中 vis[v]=1; cnt++; if(cnt==n-1) break; temp=v; for(int i=1;i<=n;i++) { if(!vis[i]&&dis[temp]+g[temp][i]<dis[i]) { dis[i]=dis[temp]+g[temp][i]; pre[i]=temp; q.push({temp,i,dis[temp]+g[temp][i]}); } }//更新优先队列 } for(int i=2;i<=n;i++) { if(dis[i]==INF) { cout<<"inf: 1->"<<i<<endl; continue; }//如果源1到该顶点没有路，则输出："inf: 1->u" stack<int> s; int t=i; while(t!=0) { s.push(t); t=pre[t]; } cout<<dis[i]<<": "<<s.top(); s.pop(); while(!s.empty()) { cout<<"->"; cout<<s.top(); s.pop(); } cout<<endl; }//输出结果 return 0; } 修改这个代码 使其最后一个结点为源节点

修改后的代码如下：

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>

using namespace std;

const int INF = 0x3f3f3f3f; // 无穷大
int n, g[105][105];
int dis[105], pre[105], vis[105];

struct edge {
    int u, v, d; // 边的起点、终点、权值
    bool operator < (const edge &a) const {
        return d > a.d;
    }
};

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> g[i][j];
            if (g[i][j] == 0) {
                g[i][j] = INF;
            }
        }
    }
    priority_queue<edge> q; // 优先队列
    int temp = n; // 当前顶点为终点n
    int cnt = 0; // 当前边数
    for (int i = 1; i <= n; i++) {
        if (i != temp) {
            pre[i] = temp;
            dis[i] = g[temp][i];
            q.push({temp, i, g[temp][i]});
        }
    }
    while (!q.empty()) {
        edge t = q.top();
        q.pop();
        int v = t.v;
        if (vis[v]) {
            continue;
        } // 已经在已加入点的集合当中
        vis[v] = 1;
        cnt++;
        if (cnt == n - 1) {
            break;
        }
        temp = v;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && dis[temp] + g[temp][i] < dis[i]) {
                dis[i] = dis[temp] + g[temp][i];
                pre[i] = temp;
                q.push({temp, i, dis[temp] + g[temp][i]});
            } // 更新优先队列
        }
    }
    for (int i = 1; i < n; i++) {
        if (dis[i] == INF) {
            cout << "inf: " << n << "->" << i << endl;
            continue;
        } // 如果结点n到该顶点没有路，则输出："inf: n->u"
        stack<int> s;
        int t = i;
        while (t != n) {
            s.push(t);
            t = pre[t];
        }
        cout << dis[i] << ": " << n;
        while (!s.empty()) {
            cout << "->" << s.top();
            s.pop();
        }
        cout << endl;
    } // 输出结果
    return 0;
}

需要注意的是，修改了起点之后，我们需要将循环体中的变量temp初始化为终点n，且在最后的输出结果中，需要将起点1改为终点n。