题目

解决

思路

Dijkstra + DFS保存下来的路径是倒着存储的

实现

Code1

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N = 510; const int INF = 1000000000; int n, m, st, ed; int G[N][N]; int cost[N][N]; int d[N]; int minCost = INF; bool vis[N] = {false}; vector<int> pre[N]; vector<int> path, tempPath; void Dijkstra(int s){ fill(d, d+N, INF); d[s] = 0; for(int i=0; i<n; i++){ int u = -1; int MIN = INF; 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(d[u] + G[u][v] < d[v]){ d[v] = d[u] + G[u][v]; pre[v].clear(); pre[v].push_back(u); }else if(d[u] + G[u][v] == 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--){ int id = tempPath[i]; int idNext = tempPath[i-1]; tempCost += cost[id][idNext]; } 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(){ scanf("%d%d%d%d", &n, &m, &st, &ed); int u, v; fill(G[0], G[0]+N*N, INF); fill(cost[0], cost[0]+N*N, INF); for(int i=0; i<m; i++){ scanf("%d%d", &u, &v); scanf("%d%d", &G[u][v], &cost[u][v]); G[v][u] = G[u][v]; cost[v][u] = cost[u][v]; } Dijkstra(st); DFS(ed); for(int i=path.size()-1; i>=0; i--){ printf("%d ", path[i]); } printf("%d %d\n", d[ed], minCost); return 0; }