1030. Travel Plan (30) dijkstra记录所有最短路径，dfs筛选最优路径即可
#include <cstdio> #include <vector> #define N 500+1 #define INF 999999999 std::vector<std::vector<int>> path(N); std::vector<int> sp; std::vector<int> ans; int n,m,s,d,mincost=INF,distance=0; int a[N][N],dist[N],visited[N],cost[N][N]; void dfs(std::vector<std::vector<int>> &path,int v) { sp.push_back(v); if(v==s) { int curcost=0; auto r=sp.begin(); auto f=sp.begin()+1; while(f!=sp.end()) { curcost+=cost[*r][*f]; r=f;++f; } if(curcost<mincost) { mincost=curcost; ans=sp; } return; } for(auto it=path[v].begin();it!=path[v].end();++it) { dfs(path,*it); sp.pop_back(); } } int main() { scanf("%d %d %d %d",&n,&m,&s,&d); for(int i=0;i<n;++i) { for(int j=0;j<n;++j) { if(i==j) a[i][j]=0; else a[i][j]=INF; } } for(int i=0;i<m;++i) { int u,v,dis,ct; scanf("%d %d %d %d",&u,&v,&dis,&ct); a[u][v]=a[v][u]=dis; cost[u][v]=cost[v][u]=ct; } for(int i=0;i<n;++i) { if(a[i][s]<INF) path[i].push_back(s); dist[i]=a[s][i]; } int i,j,v,w; visited[s]=1; for(i=1;i<n;++i) { int min=INF; for(j=0;j<n;++j) { if(min>dist[j]&&!visited[j]) { min=dist[j]; v=j; } } visited[v]=1; for(w=0;w<n;++w) { if(!visited[w]&&a[v][w]<INF) { if(dist[w]>dist[v]+a[v][w]) { dist[w]=dist[v]+a[v][w]; path[w].clear(); path[w].push_back(v); } else if(dist[w]==dist[v]+a[v][w]) path[w].push_back(v); } } } dfs(path,d); auto it=ans.end()-1; while(it>=ans.begin()) { if(it>ans.begin()) { auto r=it-1; distance+=a[*it][*r]; } printf("%d ",*it); it--; } printf("%d %d",distance,mincost); return 0; }