鏈接：https://www.nowcoder.com/questionTerminal/a7052c5bd8634edb9ccee711a5c1ea54
來源：牛客網

短最優升級路徑

題目描述：游戲網站提供若干升級補丁，每個補丁大小不一，玩家要升級到最新版，如何選擇下載哪些補丁下載量最小。

輸入：

第一行輸入????????????????

第一個數為用戶版本?第二個數為最新版本，空格分開

接著輸入N行補丁數據 ??????

第一個數補丁開始版本 第二個數為補丁結束版本 第三個數為補丁大小，空格分開

輸出：

對于每個測試實例，輸出一個升級路徑以及最后實際升級的大小

樣例輸入：

1000 1050

1000 1020 50

1000 1030 70

1020 1030 15

1020 1040 30

1030 1050 40

1040 1050 20

樣例輸出：

1000->1020->1040->1050(100)

迪杰斯特拉最短路徑算法 建立鄰接矩陣，標識版本間的來去路線，求最初版本到最末版本之間的最短路徑。

在dijkstra算法模板的基礎上加上一個pre數組，用于記錄該節點的上一個節點，即該點是經過哪一點才到達該點的。pre數組具體在邊松弛的過程中進行重新賦值，松弛成功就將pre值記錄k點，及該點是由起點經過k點后所得到的。最后把pre數組中的值遞歸輸出一遍即可。

#include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=10000; #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f map<int,int> mp,rmp; int road[maxn][maxn]; int dis[maxn]; bool vis[maxn]; int pre[maxn]; int n;void dijkstra(int s,int e) {//s為起點，e為終點memset(vis, false, sizeof(vis));//標記是否求出最短路徑vis[s] = true;//標記起點到這一點的最小距離已經求出for(int i = 1; i < n; i++){dis[i] = road[s][i];//初始化起點到每一個點的距離pre[i]=s;//初始化路徑，每個點的上一個點為起點}for(int u = 1; u < n-1; u++){int minD =inf ,k = -1;for(int i = 1; i< n; i++){ //尋找沒有訪問過的最短路if(!vis[i]&&dis[i]<minD){k = i;//記錄下標minD = dis[i];//記錄最小值}}if(k==e) break;vis[k] = true;//標記已經訪問過//松弛操作for(int i = 1; i< n; i++){if(!vis[i]&&dis[k]+road[k][i]<dis[i]){dis[i]=dis[k]+road[k][i];pre[i]=k;}//if}//for} }void print(int cur){if(cur==1){printf("%d",rmp[cur]);return ;}print(pre[cur]);printf("->%d",rmp[cur]); }int main(){int start,end;n=1;scanf("%d%d",&start,&end);rmp.clear();mp.clear();mp[start]=n;rmp[n]=start;n++;mp[end]=n;rmp[n]=end;n++;int N=(end-start)/10;memset(road,INF,sizeof road);for(int i=0;i<=N;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);if(!mp[u]) {mp[u]=n;rmp[n]=u;n++;}if(!mp[v]) {mp[v]=n;rmp[n]=v;n++;}road[mp[u]][mp[v]]=road[mp[v]][mp[u]]=min(road[mp[v]][mp[u]],w);}for(int i=1;i<n;i++){for(int j=1;j<n;j++)printf("%d ",road[i][j]==INF?-1:road[i][j]);printf("\n");}dijkstra(mp[start],mp[end]);if(dis[mp[end]]==INF)printf("-1");else{print(mp[end]);printf("(%d)\n",dis[mp[end]]);}return 0; }

總結

以上是生活随笔為你收集整理的牛客网 短最优升级路径 【Dijkstra算法】+【路径记录】的全部內容，希望文章能夠幫你解決所遇到的問題。

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