本题来说，d+DFS的算法其实很没有必要，但是还是要学会。 dijkstra
#include<cstdio> #include<iostream> using namespace std; const int maxn=1010; const int inf=0x3fffffff; int path[maxn],G[maxn][maxn],d[maxn],c[maxn],cost[maxn][maxn],n,m,st,ed; bool vis[maxn]={false}; void dijkstra(int s) { fill(d,d+maxn,inf); fill(c,c+maxn,inf); d[s]=0; c[s]=0; for(int i=0;i<n;i++) { int min=inf,u=-1; for(int j=0;j<n;j++) { if(vis[j]==false&&d[j]<min) { u=j; min=d[j]; } } if(u==-1)return; vis[u]=true; for(int v=0;v<n;v++) { if(vis[v]==false&&G[u][v]!=inf) { if(G[u][v]+d[u]<d[v]) { d[v]=G[u][v]+d[u]; path[v]=u; c[v]=c[u]+cost[u][v]; } else if(G[u][v]+d[u]==d[v]) { if(cost[u][v]+c[u]<c[v]) { path[v]=u; c[v]=c[u]+cost[u][v]; } } } } } } void DFS(int v) { if(v==st) { printf("%d ",st); return ; } DFS(path[v]); printf("%d ",v); } int main() { int c1,c2,dis,co; cin>>n>>m>>st>>ed; fill(G[0],G[0]+maxn*maxn,inf); for(int i=0;i<m;i++) { scanf("%d %d %d %d",&c1,&c2,&dis,&co); G[c1][c2]=G[c2][c1]=dis; cost[c1][c2]=cost[c2][c1]=co; } dijkstra(st); DFS(ed); printf("%d %d",d[ed],c[ed]); }dijkstra+DFS
#include<cstdio> #include<iostream> #include<vector> using namespace std; const int maxn=1010; const int inf=0x3fffffff; int G[maxn][maxn],d[maxn],cost[maxn][maxn],n,m,st,ed,mincost=inf; vector<int> pre[maxn],path,temppath; bool vis[maxn]={false}; void dijkstra(int s) { fill(d,d+maxn,inf); d[s]=0; for(int i=0;i<n;i++) { int min=inf,u=-1; for(int j=0;j<n;j++) { if(vis[j]==false&&d[j]<min) { u=j; min=d[j]; } } if(u==-1)return; vis[u]=true; for(int v=0;v<n;v++) { if(vis[v]==false&&G[u][v]!=inf) { if(G[u][v]+d[u]<d[v]) { d[v]=G[u][v]+d[u]; pre[v].clear(); pre[v].push_back(u); } else if(G[u][v]+d[u]==d[v]) { pre[v].push_back(u); } } } } } void DFS(int v) { if(v==st) { temppath.push_back(v); int tempcost=0; for(int i=temppath.size()-1;i>0;i--) { tempcost+=cost[temppath[i]][temppath[i-1]]; } if(tempcost<mincost) { mincost=tempcost; path=temppath; } temppath.pop_back(); return; } temppath.push_back(v); for(int i=0;i<pre[v].size();i++) DFS(pre[v][i]); temppath.pop_back(); } int main() { int c1,c2,dis,co; cin>>n>>m>>st>>ed; fill(G[0],G[0]+maxn*maxn,inf); for(int i=0;i<m;i++) { scanf("%d %d %d %d",&c1,&c2,&dis,&co); G[c1][c2]=G[c2][c1]=dis; cost[c1][c2]=cost[c2][c1]=co; } dijkstra(st); DFS(ed); for(int i=path.size()-1;i>=0;i--) printf("%d ",path[i]); printf("%d %d",d[ed],mincost); }