選擇最佳路線

分析：

這是一道圖論中的最短路徑問題，目標是在給定的公交網絡中，找到從琪琪家附近的車站出發，到她朋友家附近車站（編號為?s?）的最短時間。以下是對該問題的詳細分析：

問題關鍵信息

圖的結構：

圖由?n?個車站（節點）和?m?條公交線路（有向邊）組成，邊是單向的，且兩節點間可能有多條邊。

每條邊（公交線路）有起點?p、終點?q?和花費時間?t?的屬性。

起始點和終點：

終點是朋友家附近的車站，編號為?s?。

起始點可以從琪琪家附近的?w?個車站中任選一個。

求解目標：計算從可選擇的起始點到終點的最短時間。

解題思路

建圖：使用鄰接表或鄰接矩陣來存儲圖的信息。對于每條公交線路（p,?q,?t），在圖中添加從節點?p?到節點?q?、權重為?t?的有向邊。

最短路徑算法：可以使用 Dijkstra 算法（適用于沒有負權邊的情況，本題中時間不會為負）或 Bellman - Ford 算法（可以處理負權邊，但本題不需要）。從琪琪家附近的每個車站（起始點）開始，計算到其他所有車站的最短距離。（使用虛擬節點）

結果處理：在計算出從每個起始點到所有車站的最短距離后，找到到達編號為?s?的車站的最短時間。

偽代碼：

拯救大兵瑞恩：

分析：

這是一道基于圖論和搜索算法的迷宮路徑求解問題，核心在于在帶有門和鑰匙限制的迷宮中，找到從起點到終點的最短路徑。以下是對該問題的詳細分析：

問題關鍵信息

- 迷宮結構： - 迷宮是一個 $N times M$ 的長方形區域，由 $N$ 行和 $M$ 列的單元組成，每個單元位置用有序數對（行號，列號）表示。

- 相鄰單元間可能互通、有鎖著的門或不可逾越的墻，門是無向的，可雙向通過。 - 鑰匙與門： - 迷宮中部分單元存放鑰匙，同一單元可能有多把鑰匙。

- 門分為 $P$ 類，打開同一類門的鑰匙相同，不同類門鑰匙不同。

- 起點與終點：

- 起點為迷宮西北角的 $(1, 1)$ 單元，麥克可直接進入。

- 終點是迷宮東南角的 $(N, M)$ 單元，大兵瑞恩昏迷于此。

?- 移動時間：麥克從一個單元移動到相鄰單元的時間為 1，拿鑰匙和開門時間忽略不計。 - 求解目標：設計算法找到麥克從起點到終點的最快（最短時間）路徑。

解題思路

1. 狀態表示：除了記錄位置坐標 $(x, y)$ 外，還需記錄當前擁有的鑰匙狀態。可以用一個二進制數或集合來表示擁有哪些類別的鑰匙，假設鑰匙類別從 0 到 $P - 1$ 編號，二進制數中第 $i$ 位為 1 表示擁有第 $i$ 類鑰匙。這樣每個狀態可以表示為 $(x, y, key_status)$ 。

2. 建圖或搜索空間構建：根據迷宮的連通性、門和鑰匙的關系，構建搜索空間。對于每個單元，考慮其相鄰單元，若相鄰單元間是墻則不可達；若是門，需判斷是否有對應的鑰匙；若是通路則可直接到達。

3. 搜索算法：使用廣度優先搜索（BFS）算法較為合適，因為 BFS 能保證找到的路徑是最短的（在單位移動時間的情況下）。從起點 $(1, 1, 初始鑰匙狀態)$ 開始搜索，將可達的狀態加入隊列，不斷擴展，直到找到終點 $(N, M, _)$ （鑰匙狀態任意）。

4. 剪枝優化：為了減少搜索量，可以進行一些剪枝操作。比如記錄已經訪問過的狀態 $(x, y, key_status)$ ，如果再次遇到相同狀態則不再重復處理。

偽代碼：

最短路計數：

分析：

這是一道圖論中的最短路徑計數問題，要求計算從頂點1到圖中其他每個頂點的最短路徑的數量。由于圖是無向無權的，所以可以使用廣度優先搜索（BFS）算法來解決。以下是詳細分析：

問題關鍵信息

- 圖的屬性：

- 給定一個包含 $N$ 個頂點（編號為 1 到 $N$）和 $M$ 條邊的無向無權圖。

- 圖中可能存在自環（頂點自身到自身的邊）和重邊（兩個頂點之間有多條邊）。 - 起始頂點和目標：

- 起始頂點為頂點 1 。

- 目標是計算從頂點 1 到其他每個頂點的最短路徑的數量。

- 輸出要求： - 輸出 $N$ 行，每行一個非負整數，表示從頂點 1 到對應頂點的不同最短路徑的數量，結果對 100003 取模。 - 如果無法到達某個頂點，則輸出 0 。

?解題思路

1. 建圖：使用鄰接表來存儲圖的結構，對于每一條邊 $(x, y)$，在鄰接表中分別在頂點 $x$ 和頂點 $y$ 的鄰接表中添加對方。

2. BFS 搜索：從頂點 1 開始進行 BFS 。在 BFS 的過程中，維護兩個數組： - `dist[i]` 表示從頂點 1 到頂點 $i$ 的最短距離，初始化為無窮大，頂點 1 的距離初始化為 0 。 - `count[i]` 表示從頂點 1 到頂點 $i$ 的最短路徑的數量，初始化為 0 ，頂點 1 的數量初始化為 1 。

3. 狀態更新：在 BFS 遍歷過程中，對于當前頂點 $u$ 的每個鄰接頂點 $v$ ： - 如果 `dist[v]` 為無窮大，說明這是第一次訪問到頂點 $v$，則 `dist[v] = dist[u] + 1`，`count[v] = count[u]` 。 - 如果 `dist[v] = dist[u] + 1`，說明找到了一條新的最短路徑，那么 `count[v] = (count[v] + count[u]) % 100003` 。

4. 輸出結果：遍歷頂點 1 到頂點 $N$，輸出 `count[i]` ，如果 `dist[i]` 仍然是無窮大，說明無法到達頂點 $i$，則輸出 0 。

偽代碼：

觀光

分析：

這是一道圖論中的路徑計數問題，要求在給定的公交路線圖中，找出從起始城市?S?到目標城市?F?的滿足特定距離條件（最短路徑或比最短路徑多一個單位長度）的路徑數量。下面是詳細分析：

問題關鍵信息

• 圖的屬性：
  • 公交路線圖可看作一個圖，城市為頂點，公交路線為邊，邊有權重（代表路程長度）。
  • 圖中可能存在重邊和不同的路徑組合。
• 起始和目標：
  • 起始城市為?S，目標城市為?F。
• 路徑條件：
  • 旅客可選的路徑需滿足：要么是?S?到?F?的最短路徑，要么總路程僅比最短路徑多一個單位長度。
• 求解目標：
  • 計算滿足上述條件的不同路徑的數量。

解題思路

1. 計算最短路徑：使用 Dijkstra 算法或 Bellman - Ford 算法（本題邊權非負，Dijkstra 更高效）來計算從城市?S?到其他所有城市的最短距離，記為?dist[i]，其中?i?表示城市編號，這樣能得到?S?到?F?的最短距離?min_dist。
2. 路徑搜索與計數：使用深度優先搜索（DFS）或廣度優先搜索（BFS）遍歷圖，在搜索過程中記錄路徑長度。
   • 當路徑長度等于?min_dist?時，路徑計數加 1。
   • 當路徑長度等于?min_dist + 1?時，路徑計數也加 1。
   • 為避免重復計數，可使用一個標記數組記錄已經訪問過的城市狀態（對于每個城市記錄當前路徑長度下是否已訪問）。
3. 輸出結果：將滿足條件的路徑數量輸出。

偽代碼：