Board logo

標題: 資料結構 405 旅遊路線規劃 [打印本頁]
作者: may    時間: 5 天前 11:44     標題: 資料結構 405 旅遊路線規劃

資料結構 405 旅遊路線規劃

1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 市府新團隊上路後就積極推廣市民單車運動，去年委由專家決選出行政區內的幾處重要景點，每一個景點都有編號（1,2,...）。近期也已經佈建好景點與景點之間的單車專用道（雙向），方便市民與外地遊客利用單車進行城市的深度旅遊。

(2) 班上預計在期中考後辦理單車班遊，目前同學們已經開會決定了「起點（S）」與「終點（T）」（起點與終點不同）。

(3) 現在，需要你幫忙規劃景點的參觀路線，目標是找出「一條最短的參觀路線」：由起點（S）出發，經過其他景點（不用全部都經過），最後到達終點（T）。

3. 輸入輸出：
輸入說明
第 1 列：包含兩個正整數 M、N，以半形空白間隔。其中 M 為景點的數量、N 為單車車道的數量，且 5 ≤ M ≤ 30，4 ≤ N ≤ 200。
第 2 列：包含兩個正整數 S、T，以半形空白間隔。其中 S 為起點（景點編號），T 為終點（景點編號），且 1 ≤ S, T ≤ M。
第 3~N+2 列：每一列包含三個數字 a、b 和 d，以半形空白間隔。代表景點 a 與景點 b 之間鋪設的專用車道，其距離為 d 公里，其中 a、b 為景點編號，皆為整數（1 ≤ a, b ≤ M），而距離 d 為大於 0 的整數或浮點數。

輸出說明
最短的參觀路線長度，輸出結果以公里為單位，並四捨五入至小數點後第一位。

範例輸入1
6 8
1 6
1 2 10
1 3 15
2 4 12
2 6 15
3 5 10
4 5 2.58
4 6 1
6 5 5
範例輸出1
23.0
範例輸入2
7 9
1 7
1 2 2.1
1 3 6
2 4 4.9
3 4 8
4 5 10.0
4 6 15
5 6 6
5 7 3.14159
6 7 6
範例輸出2
20.1
作者: may    時間: 5 天前 11:58

  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <queue>
  4. //#include <iomanip>

  6. #include <bits/stdc++.h>
  7. using namespace std;

  9. const double INF = numeric_limits<double>::max(); // 無限大

  11. struct Edge {
  12.     int to;
  13.     double weight;
  14. };

  16. struct Node {
  17.     int id;
  18.     double dist;
  19.     bool operator>(const Node& other) const {
  20.         return dist > other.dist; // 優先隊列最小堆
  21.     }
  22. };

  24. int main() {
  25.     int M, N; // 景點數量 M，單車車道數量 N
  26.     cin >> M >> N;

  28.     int S, T; // 起點 S，終點 T
  29.     cin >> S >> T;

  31.     vector<vector<Edge>> graph(M + 1); // 使用鄰接表儲存圖

  33.     // 讀取車道資訊
  34.     for (int i = 0; i < N; i++) {
  35.         int a, b;
  36.         double d;
  37.         cin >> a >> b >> d;
  38.         graph[a].push_back({b, d});
  39.         graph[b].push_back({a, d}); // 雙向道路
  40.     }

  42.     // **Dijkstra 演算法**
  43.     priority_queue<Node, vector<Node>, greater<Node>> pq;
  44.     vector<double> dist(M + 1, INF);
  45.     dist[S] = 0;
  46.     pq.push({S, 0});

  48.     while (!pq.empty()) {
  49.         Node cur = pq.top();
  50.         pq.pop();

  52.         int u = cur.id;
  53.         double d = cur.dist;

  55.         if (d > dist[u]) continue; // 若當前距離大於已知最短距離，則跳過

  57.         for (const Edge& e : graph[u]) {
  58.             int v = e.to;
  59.             double newDist = dist[u] + e.weight;
  60.             if (newDist < dist[v]) {
  61.                 dist[v] = newDist;
  62.                 pq.push({v, newDist});
  63.             }
  64.         }
  65.     }

  67.     // **輸出結果**
  68.     cout << fixed << setprecision(1) << dist[T] << endl;

  70.     return 0;
  71. }
複製代碼
回復 1# may
--------------------------------------------------------
解題思路
輸入處理：

讀取景點數量
M 和車道數量
N。

讀取起點
S 和終點
T。

使用鄰接表來存儲圖的結構（因為邊數
N 可能遠大於點數
M）。

Dijkstra 演算法：

使用 最小堆 (priority_queue) 來優化最短路徑搜尋。

每次從當前最短距離的節點開始，更新其相鄰節點的距離。

當處理完所有可能的路徑後，終點
T 的距離即為答案。

輸出：

若能到達終點
T，則輸出四捨五入到小數點後 1 位的最短距離。
_______________________________________
程式解釋
讀取輸入：

先讀取 景點數量
M 和 車道數量
N。

再讀取 起點
S 和 終點
T。

用 鄰接表 (vector of vectors) 存儲圖的結構，因為
M 最大是 30，但
N 可以到 200，用鄰接表更省空間。

建構圖 (Graph Representation)

讀取每條道路 (a, b, d)，並在 graph[a] 和 graph 中加入該邊，因為是雙向道路。

Dijkstra 演算法：

使用最小堆 (priority_queue) 來優化最短路徑計算。

維護距離陣列 dist[]，用來記錄從 S 到其他景點的最短距離。

優先隊列存儲 (景點編號, 當前距離)，確保每次處理當前最短距離的節點。

若找到更短的路徑，則更新 dist[v]，並將 (v, newDist) 放入最小堆。

輸出結果：

cout << fixed << setprecision(1) << dist[T] << endl;

四捨五入到小數點後 1 位。

時間複雜度分析
Dijkstra 演算法 (Priority Queue)：

O(NlogM)，因為 priority_queue 操作複雜度為

O(logM)，最多有
N 條邊需要處理。

最壞情況：

N=200,M=30，最多
200log30≈200×5=1000 次操作，運行時間 極快。
----------------------------------------------------------
測資:
測試範例
輸入 00
6 8
1 6
1 2 10
1 3 15
2 4 12
2 6 15
3 5 10
4 5 2.58
4 6 1
6 5 5
輸出 00
23.0
輸入01
7 9
1 7
1 2 2.1
1 3 6
2 4 4.9
3 4 8
4 5 10.0
4 6 15
5 6 6
5 7 3.14159
6 7 6
輸出 01
20.1
總結
Dijkstra 適合求最短路徑，使用 最小堆 加速查詢。

鄰接表節省空間，適用於 稀疏圖 (邊數比點數多)。

使用 setprecision(1) 來確保輸出格式正確。

這樣，我們就完成了 城市單車旅遊規劃問題！



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2