回復 1# may - #include <bits/stdc++.h>
- //#include <iostream>
- //#include <vector>
- //#include <numeric> // 用於 accumulate 計算數值總和
- //#include <algorithm>
- using namespace std;
- vector<vector<int>> graph; // 存儲無向圖（鄰接表）
- vector<int> bestPath; // 最佳路徑
- int maxLength = 0; // 最長路徑長度
- int maxSum = 0; // 景點編號加總最大值
- // 深度優先搜尋（DFS）
- void dfs(int node, int end, vector<int>& path, vector<bool>& visited) {
- path.push_back(node); // 加入當前景點
- visited[node] = true; // 標記該景點已拜訪
- if (node == end) { // 抵達終點
- int pathLength = path.size();
- int pathSum = accumulate(path.begin(), path.end(), 0);
- // 更新最佳路徑條件：
- // 1. 若新路徑長度較長，則更新
- // 2. 若長度相同但編號加總較大，也更新
- if (pathLength > maxLength || (pathLength == maxLength && pathSum > maxSum)) {
- maxLength = pathLength;
- maxSum = pathSum;
- bestPath = path;
- }
- } else { // 繼續探索其他鄰近景點
- for (int neighbor : graph[node]) {
- if (!visited[neighbor]) { // 確保不重複拜訪
- dfs(neighbor, end, path, visited);
- }
- }
- }
- path.pop_back(); // 回溯：移除當前景點
- visited[node] = false; // 取消標記
- }
- int main() {
- int N, M;
- cin >> N >> M;
- graph.assign(N, vector<int>()); // 初始化鄰接表
- // 讀取 M 條道路資訊
- for (int i = 0; i < M; i++) {
- int u, v;
- cin >> u >> v;
- graph[u].push_back(v);
- graph[v].push_back(u); // 雙向通行
- }
- int S, E;
- cin >> S >> E;
- vector<int> path; // 暫存路徑
- vector<bool> visited(N, false); // 紀錄景點是否被拜訪
- dfs(S, E, path, visited); // 執行 DFS
- // 輸出最佳路徑
- for (size_t i = 0; i < bestPath.size(); i++) {
- cout << bestPath[i] << (i == bestPath.size() - 1 ? "\n" : " ");
- }
- return 0;
- }
解題思路
建立圖的鄰接表
使用 vector<vector<int>> graph 來存儲無向圖的連結關係。
使用 DFS（深度優先搜尋）找出所有路徑
透過 DFS 遍歷所有從 S 到 E 的可能路徑，避免重複經過同一個景點。
遇到終點時，根據條件檢查是否更新最佳路徑。
選擇最佳路徑
記錄 最大景點數量 的路徑。
若有多條符合條件的路徑，選擇 景點編號加總較大 的。
測資
測試00
輸入
6 9
0 1
0 2
0 3
0 4
1 4
2 4
3 4
3 5
4 5
0 5
預期輸出
0 2 4 3 5
解釋
所有路徑長度最大為 5
0 → 1 → 4 → 3 → 5（景點總和 = 13）
0 → 2 → 4 → 3 → 5（景點總和 = 14）
選擇編號總和較大的路徑 0 2 4 3 5
測試01
輸入
4 4
0 1
0 2
1 3
2 3
1 3
預期輸出
1 0 2 3
解釋
所有路徑長度最大為 4
0 → 1 → 3 → 2（景點總和 = 6）
1 → 0 → 2 → 3（景點總和 = 6）
景點總和相同，但 1 0 2 3 字典序較大，所以選擇此路徑。
測試 02
輸入
5 5
0 1
1 2
2 3
3 4
0 4
0 4
預期輸出
0 1 2 3 4
解釋
最長路徑：0 → 1 → 2 → 3 → 4（長度 5）
唯一的最長路徑，直接輸出
測試 03
輸入
7 8
0 1
1 2
2 3
3 6
0 4
4 5
5 6
2 5
0 6
預期輸出
0 1 2 5 6
解釋
可能的最長路徑：
0 → 1 → 2 → 3 → 6（景點總和 = 12）
0 → 1 → 2 → 5 → 6（景點總和 = 14）
選擇景點總和較大的 0 1 2 5 6
測試04
輸入
8 10
0 1
1 2
2 3
3 7
0 4
4 5
5 6
6 7
2 6
1 5
0 7
預期輸出
0 1 5 6 7
解釋
可能的最長路徑：
0 → 1 → 2 → 3 → 7（景點總和 = 13）
0 → 1 → 5 → 6 → 7（景點總和 = 19）
選擇景點總和較大的 0 1 5 6 7
這 5 組測資涵蓋 基本測試、分岔選擇、最大景點加總比對 等情境，適用於完整測試程式的正確性。 |
