https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392
先跑一下Dijkstra()
然后再dfs()一下求最短路下的最小花費即可，記得保存路徑。

#include<bits/stdc++.h> using namespace std; const int N=1e2*5+10; const int inf=0x3f3f3f3f; int dist[N],g[N][N],price[N][N],n,m,s,d; int st[N],ans=inf; vector<int>paths,temp; void Dijkstra() {memset(dist,0x3f,sizeof dist);dist[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[j]<dist[t])) t=j;st[t]=1;for(int j=0;j<n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);} } void dfs(int u,int father,int sum) {if(u==d){if(sum<ans) {ans=sum,paths=temp;paths.push_back(d);}return;}for(int i=0;i<n;i++){if(i==father) continue;//避免走回路if(dist[i]==dist[u]+g[u][i])//是最短路上的點{temp.push_back(u);dfs(i,u,sum+price[u][i]);temp.pop_back();}} } int main(void) {cin>>n>>m>>s>>d;memset(g,0x3f,sizeof g);memset(price,0x3f,sizeof price);for(int i=0;i<m;i++){int a,b,c,w; cin>>a>>b>>c>>w;if(g[a][b]>c){g[a][b]=g[b][a]=c;price[a][b]=price[b][a]=w;}}Dijkstra();dfs(s,-1,0);for(int i=0;i<paths.size();i++) cout<<paths[i]<<" ";cout<<dist[d]<<" "<<ans;return 0; }

總結

以上是生活随笔為你收集整理的1030 Travel Plan (30 分) 【难度: 中 / 知识点: 最短路】的全部內容，希望文章能夠幫你解決所遇到的問題。

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