1030 Travel Plan（dijsktra + dfs/bfs + 回溯）

 题面意思比较清晰，就是优先最短路，同距离取最小花费。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m, s, d;
 4 typedef pair<int, int> pii;
 5 vector<pii> graph[505];
 6 set<pii> min_heap;
 7 int cost[505][505] = {0};
 8 vector<bool> visited(505, false);
 9 vector<bool> dfs_visited(505, false);
10 vector<int> dist(505,0x3f3f3f);
11 vector<int> prefix[505]; //记录前结点的队列
12 vector<int> result; //记录最终路径
13 int minimum = 0x3f3f3f; //记录最小花费
14 
15 void dijkstra(int start) {
16     visited[start] = true;
17     dist[start] = 0;
18     min_heap.insert(make_pair(0,start));
19     while(!min_heap.empty()) {
20         auto iter = min_heap.begin();
21         int root = iter -> second;
22         visited[root] = true;
23         min_heap.erase(iter);
24         for(auto i : graph[root]) {
25             int child = i.first;
26             int dis = i.second;
27             if (!visited[child]) {
28                 if (dist[child] > dist[root] + dis) {
29                     prefix[child].clear();
30                     min_heap.erase(make_pair(dist[child], child));
31                     dist[child] = dist[root] + dis;
32                     min_heap.insert(make_pair(dist[child], child));
33                     prefix[child].push_back(root);
34                 } else if (dist[child] == dist[root] + dis) { //同距离添加到前缀队列中
35                     prefix[child].push_back(root);
36                 }
37             }
38         }
39     }
40 }
41 void dfs(int p, int end, int cnt, vector<int> path) {
42     dfs_visited[p] = true;
43     if (p == end) {
44         if (cnt < minimum) {
45             result = path;
46             minimum = cnt;
47         }
48         return;
49     }
50 
51     for (auto i : prefix[p]) {
52         if (!dfs_visited[i]) {
53             vector<int> temp = path;
54             temp.push_back(i);
55             dfs(i, end, cnt + cost[p][i], temp);
56             dfs_visited[i] = false;
57         }
58     }
59 }
60 int main() {
61     cin >> n >> m >> s >> d;
62     for (int i = 0; i < m; ++ i) {
63         int c1, c2, dis, cos;
64         cin >> c1 >> c2 >> dis >> cos;
65         graph[c1].push_back(make_pair(c2, dis));
66         graph[c2].push_back(make_pair(c1, dis));
67         cost[c1][c2] = cos;
68         cost[c2][c1] = cos;
69     }
70     dijkstra(s);
71     vector<int> temp;
72     temp.push_back(d);
73     dfs(d, s, 0, temp); //由于记录的是前结点，遍历时从目的到起点
74     reverse(result.begin(),result.end()); //反转一下路径
75     for (auto i : result) {
76         cout << i << " ";
77     }
78     cout << dist[d] << " " << minimum;
79 }