L2-001 緊急救援 分數 25 作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖。在地圖上顯示有多個分散的城市和一些連接城市的快速道路。每個城市的救援隊數量和每一條連接兩個城市的快速道路長度都標在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊儘快趕往事發地，同時， ...
L2-001 緊急救援 分數 25
作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖。在地圖上顯示有多個分散的城市和一些連接城市的快速道路。每個城市的救援隊數量和每一條連接兩個城市的快速道路長度都標在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊儘快趕往事發地，同時，一路上召集儘可能多的救援隊。
輸入格式:
輸入第一行給出4個正整數N、M、S、D，其中N（2≤N≤500）是城市的個數，順便假設城市的編號為0 ~ (N−1)；M是快速道路的條數；S是出發地的城市編號；D是目的地的城市編號。
第二行給出N個正整數，其中第i個數是第i個城市的救援隊的數目，數字間以空格分隔。隨後的M行中，每行給出一條快速道路的信息，分別是：城市1、城市2、快速道路的長度，中間用空格分開，數字均為整數且不超過500。輸入保證救援可行且最優解唯一。
輸出格式:
第一行輸出最短路徑的條數和能夠召集的最多的救援隊數量。第二行輸出從S到D的路徑中經過的城市編號。數字間以空格分隔，輸出結尾不能有多餘空格。
輸入樣例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2輸出樣例:
2 60
0 1 3
解題思路：
從題目信息中可得到"道路長度"和"城市救援隊"這倆個玩意，於是可以聯想到帶權圖與最短路徑問題，我們可以將城市看作節點，道路看作連接節點之間的路徑，而每個城市都有一定數量的救援隊(城市的權值）同時每條道路都有距離，與此同時根據該圖不可能存在負權值的邊，而且起點與終點是固定的，那麼根據這些信息我們可以確定本題需要用到Dijkstra演算法。
與此同時在Dijkstra演算法基礎上需要考慮三個變數，一個是最短路徑的數量road[]，另一個是在最短路徑的中救援隊最多的數量total[]，最後一個是前面倆個前提下的路徑path[]
於是我在這道題中還用使用到了優先隊列priority_queue函數，後來總結髮現其實這道題還有動態規劃的思想在裡面，如果還打算優化的話還能使用弗洛伊德+迪傑斯特拉組合或最小索引堆來進行演算法效率的提升（但由於本人技術實在有限就沒考慮那麼多了T.T）
代碼部分：
1 //#include<bits/stdc++.h> 不建議使用萬能頭文件 2 #include<iostream> 3 #include<set> 4 #include<cstring> 5 #include<queue> 6 #define ll long long; // 定義long long類型 7 using namespace std; 8 9 const int inf = 0x3f3f3f3f;//無窮大 10 typedef pair<int, int>PII; 11 int n, m, s, d; //dis[i]表示當前起點到i點的最短距離 12 int mp[510][510], vis[510], dis[510];//vis數組的作用是記錄每個節點是否已被訪問過。在Dijkstra演算法中，每次從隊列中取出距離起點最短的節點時，需要判斷該節點是否已經被訪問過。若該節點已被訪問過，則可以直接跳過，因為它的最短路徑已經求得，不需要再次計算。因此，vis數組可以避免重覆計算，提高程式的效率。 13 int total[510], city[510], path[510], road[510];//road記錄從起點到每個節點的最短路徑數量,path[i]表示i節點的最短前驅節點,total[i] 表示從起點到i節點的最短路徑的救援人員數總和 14 15 void dijkstra() 16 { 17 memset(dis, 0x3f, sizeof(dis)); // 初始化距離為無窮大 18 total[s] = city[s]; // 初始點的總點權值為其本身的點權值 19 path[s] = -1; // 初始點沒有前驅節點 20 road[s] = 1; // 初始點到達方式為一種 21 dis[s] = 0; // 起點到起點的距離為0 22 //採用優先隊列的路線是：先摸出第一條最短路徑，(因為這道題還需要找相同距離的可能以及相同距離中救援隊最多的情況)所以還需要依次再摸出第二條第三條...的最短路徑 23 //也就是說最短路徑的下一個最短 節點會被優先訪問 24 priority_queue<PII>q;//優先隊列當存儲的是一組數據時預設第一個數據是權值，存儲的是pair類型（距離，節點） 用堆q存儲最短距離節點(當節點數量多時用最短距離優先隊列可以提高效率) 25 q.push({ 0,s });// 將起點加入隊列 26 while (q.size()) 27 { 28 int now = q.top().second; // 取出隊首元素的節點 29 q.pop(); // 刪除隊首元素 30 if (vis[now]) // 若當前節點已被訪問過，則跳過 31 continue; 32 vis[now] = 1; // 標記當前節點已被訪問 33 for (int i = 0; i < n; i++) 34 { 35 if (mp[now][i])//(判斷now到i是否存在路徑)用now節點去訪問所有的節點來找到最短路徑 36 { 37 if (dis[i] > dis[now] + mp[now][i]) // (dis[i]在i被訪問前都是無窮大)若通過當前節點到達其它節點更近，則更新信息 38 { 39 path[i] = now; // 更新前驅節點(i的前驅節點為now) 40 total[i] = total[now] + city[i]; // 更新總點權值(到i的救援隊總數為now的總和+城市i的數量) 41 dis[i] = dis[now] + mp[now][i]; // 更新距離 42 road[i] = road[now]; // *更新到達方式 43 if(i!=d) 44 q.push({ -dis[i],i }); // 將更新後的節點加入隊列中 (採用負數是因為希望最近的被優先處理,使得更小的距離對應更高的優先順序。) 45 } 46 else 47 { 48 if (dis[i] == dis[now] + mp[now][i]) // 若路徑相同，則更新路徑數量和總點權值 49 { 50 //也就是說在 "now到i的距離mp[now][i]+now的最短距離dis[now]等於i的最短距離dis[i]" 的前提下從起點到i的新的最短路徑數量等於 起點到i的最短路徑數road[i]加上起點到now的最短路徑數road[now] 51 //最短路徑樹的延長(可以畫張圖理解) 52 road[i] += road[now]; // ***更新路徑數量 53 if (total[i] < total[now] + city[i]) // 若當前節點的總點權值更大，則更新 54 { 55 total[i] = total[now] + city[i]; 56 path[i] = now; 57 } 58 } 59 } 60 } 61 } 62 } 63 } 64 65 int main() 66 { 67 cin >> n >> m >> s >> d; 68 for (int i = 0; i < n; i++) 69 cin >> city[i]; // 輸入每個城市的點權值 70 for (int i = 0; i < m; i++) 71 { 72 int x, y; 73 cin >> x >> y; 74 cin >> mp[x][y]; 75 mp[y][x] = mp[x][y]; // 無向圖，因此需要將兩個方向的邊權值都賦值 76 } 77 78 dijkstra(); // 調用Dijkstra演算法求解最短路徑 79 int now = d; 80 vector<int>answer; // 存儲最短路徑 81 while (now != -1) 82 { 83 answer.push_back(now); 84 now = path[now]; // 逆序遍歷路徑，找到所有經過的節點 85 } 86 cout << road[d] << " " << total[d] << endl; // 輸出到達終點的路徑數量和總點權值 87 88 for (int i = (int)answer.size() - 1; i > 0; i--) 89 cout << answer[i] << " "; 90 cout << answer[0]; // 輸出從起點到終點的最短路徑 91 92 return 0; 93 }
