考察最短路及其路徑記錄 [cpp] #include <algorithm> #include <iostream> #include <vector> #include <stack> using namespace std; #define INF 0x6FFFFFFF typedef struct Node { int dis, cost, path; Node(){dis=INF; cost=INF; path=-1;} }Node; typedef struct Edge { int end, dis, cost; Edge(int e, int d, int c){end = e; dis = d; cost = c;} }; int n, m, s, t; vector<vector<Edge>> edge; vector<int> path; vector<Node> city; std::vector<bool> visited; int FindMin() { int mmin = INF; int k = -1; for (int i = 0; i < n; ++i) { if(!visited[i] && city[i].dis < mmin) { mmin = city[i].dis; k = i; } } return k; } void Dijkstra(int s, int t) { visited.assign(n, false); city.clear(); city.resize(n); city[s].dis = 0; city[s].cost = 0; while(true) { int u = FindMin(); if(u == -1) return; visited[u] = true; for (int i = 0; i < edge[u].size(); ++i) { int v = edge[u][i].end; int cost = edge[u][i].cost; int dis = edge[u][i].dis; if (!visited[v]) { if (city[v].dis > city[u].dis+dis) { city[v].dis = city[u].dis+dis; city[v].cost = city[u].cost+cost; city[v].path = u; } else if (city[v].dis == city[u].dis+dis && city[v].cost > city[u].cost+cost) { city[v].cost = city[u].cost+cost; city[v].path = u; } } } } } void OutputPath(int t) { stack<int> ans; ans.push(t); while(city[t].path != -1) { t = city[t].path; ans.push(t); } while (!ans.empty()) { printf("%d ", ans.top()); ans.pop(); } } int main() { while (scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF) { edge.clear(); edge.resize(n); while (m--) { int u, v, d, c; scanf("%d%d%d%d",&u,&v,&d,&c); edge[u].push_back(Edge(v, d, c)); edge[v].push_back(Edge(u, d, c)); } //dijkstra Dijkstra(s, t); OutputPath(t); printf("%d %d\n",city[t].dis, city[t].cost); } return 0; }
