文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：PAT網站

分析
dijkstra模板默寫過來，然后多了一個保存路徑，使用數組pre[N]記錄最短路上每個點的前驅，通過pre數組保存到vector中

vector<int> path; //路徑放在vector中，是倒序存放的//從終點開始，起點截至for(int i = T; i!= S; i= pre[i]) path.push_back(i);

AC代碼

#include<bits/stdc++.h> using namespace std; const int N =510; bool st[N]; int d[N][N],c[N][N]; //距離 和花費（鄰接矩陣的形式） int n ,m , S, T; int dist[N]; //最短距離 int cost[N];//最小花費 int pre[N];// 路徑，記錄前驅void dijkstra(){memset(dist, 0x3f, sizeof dist);memset(cost, 0x3f, sizeof cost);dist[S] = 0 ,cost[S] =0;for(int i = 0 ;i<n; i ++){int t = -1;for(int j = 0 ;j< n; j++){if(!st[j] && (t == -1 || dist[t]>dist[j])) t =j;}st[t] =true;for(int j = 0; j< n; j++){//最短路嚴格小于if(dist[j]> dist[t] + d[t][j]){dist[j] =dist[t] +d[t][j]; //長度cost[j] =cost[t] + c[t][j];//花費pre[j] =t; //前驅是t}//有重復的最短路徑else if(dist[j] == dist[t] + d[t][j] && cost[j] > cost[t] + c[t][j]){cost[j] =cost[t] + c[t][j];pre[j] =t;}}} }int main(){cin >> n >> m >> S >> T;memset(d, 0x3f, sizeof d);//賦值無窮大memset(c, 0x3f , sizeof c);//賦值無窮大while(m--){int a, b, x, y;cin >> a >> b >> x >> y;d[a][b] =d[b][a] = min(d[a][b],x ); //防止有重邊c[a][b] = c[b][a] = min(c[a][b] ,y); //防止有重邊}dijkstra();vector<int> path; //路徑放在vector中，是倒序存放的//從終點開始，起點截至for(int i = T; i!= S; i= pre[i]) path.push_back(i);cout<<S<<" ";for(int i = path.size()-1; i>= 0; i--) cout<<path[i]<<" ";cout<<dist[T]<<" "<<cost[T];}

題目鏈接

PAT甲級1030 Travel Plan (30分)

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的PAT甲级1030 Travel Plan (30分)：[C++题解]dijkstra求单源最短路、保存路径的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。