🔗 🔴 2045. Second Minimum Time to Reach Destination 2202

tags: Weekly Contest 263 圖(Graph) BFS 最短路徑(Shortest Path)

題意

給定一個雙向連通的無向圖表示一個城市，圖中有 nn 個頂點，編號從 11 到 nn 。給定一個二維整數陣列 edgesedges ，其中 edges[i]=[ui,vi]edges[i] = [u_i, v_i] 表示頂點 uiu_i 和 viv_i 之間有一條邊。且每對頂點之間 最多 有一條邊，且沒有頂點有連接自身的邊。通過任何邊所需的時間為 timetime 分鐘。

每個頂點都有一個紅綠燈，每 changechange 分鐘會從 綠色 變為 紅色，反之亦然。所有信號燈 同步 變化。您可以在 任何時間 進入一個頂點，但只能在信號為 綠色 時離開頂點。如果信號為 綠色，您 不能等待 在頂點上，必須立即離開。

第二小值 被定義為 嚴格大於 最小值中所有值的最小值。

  • 例如，[2,3,4][2, 3, 4] 中第二小值是 33，而 [2,2,4][2, 2, 4] 中第二小值是 44。

給定 nn、edgesedges、timetime 和 changechange，返回從頂點 11 到頂點 nn 需要的 第二短時間。

注意：

  • 每個頂點可以通過 任意次，包括 11 和 nn。
  • 您可以假設在 旅程開始時，所有信號燈剛剛變為 綠色。

思路：BFS

雖然題目看似很複雜，但實際上只是最短路徑問題的變形。關鍵點在於如何處理紅綠燈的影響、以及將求最短路徑改為求次短路徑。因此我們還是可以基於 廣度優先搜索(BFS) 思路來解決這個問題，這是因為 BFS 可以找到最短路徑，而我們需要找到從頂點 11 到頂點 nn 的次短路徑。為了實現這一點，我們可以維護從頂點 11 到每個頂點的最短距離和次短距離。

在考慮從頂點 uu 走到頂點 vv 的時間時，我們需要根據當前時間 dd 判斷是否需要等待紅綠燈變換，而紅綠燈的切換次數 sw=⌊dchange⌋sw = \lfloor \frac{d}{change} \rfloor ，可以根據 swsw 的奇偶性來判斷是否需要等待紅綠燈變換，故紅綠燈的影響可以區分為兩種情況：

  • 如果到達 uu 時是紅燈，即 sw&1==1sw \And 1 == 1，我們需要等待直到下一個綠燈開始，故到達頂點 vv 的時間為 (⌊dchange⌋+1)×change+time(\lfloor \frac{d}{change} \rfloor + 1) \times change + time。
  • 如果到達 uu 時是綠燈，我們可以直接出發，故到達頂點 vv 的時間為 d+timed + time。

在 BFS 的過程中，我們使用一個佇列 qq 來保存頂點以及到達該頂點的時間。對於每個出發頂點 uu，計算其到相鄰點 vv 的時間 ndnd：

  • 如果 nd<dis[v][0]nd < dis[v][0] ，代表 ndnd 是到達 vv 的最短時間，更新 dis[v][0]dis[v][0] 並將 (v,nd)(v, nd) 加入 qq；
  • 如果 dis[v][0]<nd<dis[v][1]dis[v][0] < nd < dis[v][1] ，代表 ndnd 是到達 vv 的次短時間，更新 dis[v][1]dis[v][1] 並將 (v,nd)(v, nd) 加入 qq 。

重複上述步驟，直到 qq 為空，最終得到的 dis[v][1]dis[v][1] 即為到達 vv 的次短時間。

複雜度分析

  • 時間複雜度：O(n+m)\mathcal{O}(n + m)，其中 nn 是頂點的數量，mm 是邊的數量。
    • 在 BFS 的過程中，每個頂點最多被加入 qq 兩次，因此需要 O(n)O(n) 的時間。
    • 而在枚舉相鄰點的過程中，每條邊也最多會被考慮兩次，因此需要 O(m)O(m) 的時間。
  • 空間複雜度：O(n+m)\mathcal{O}(n + m)，其中 nn 是頂點的數量，mm 是邊的數量。
    • 建圖需要 O(m)O(m) 的空間。
    • 保存每個頂點的最短和次短距離需要 O(n)O(n) 的空間。
    • 在 BFS 的過程中，每個頂點最多被加入 qq 兩次，因此 qq 也需要 O(n)O(n) 的空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        # 建圖
        g = [[] for _ in range(n)]
        for u, v in edges:
            u, v = u - 1, v - 1
            g[u].append(v)
            g[v].append(u)

        # BFS 維護最短路徑與次短路徑
        dis = [[float('inf')] * 2 for _ in range(n)] # (最短路徑, 次短路徑)
        dis[0][0] = 0
        q = deque([(0, 0)]) # (node, distance)
        while q: 
            u, d = q.popleft()
            switch = d // change # 紅綠燈的切換次數
            if switch & 1: # 當前是紅燈，需要等待切換為綠燈才能出發
                nd = (switch + 1) * change + time
            else: # 當前是綠燈，可以直接出發
                nd = d + time
            for v in g[u]:
                if nd < dis[v][0]: # new_d 比最短路徑小，就更新最短路徑
                    dis[v][0] = nd
                    q.append((v, nd))
                elif dis[v][0] < nd < dis[v][1]: # new_d 比最短路徑大又比次短路徑小，就更新次短路徑
                    dis[v][1] = nd
                    q.append((v, nd))
        return dis[n-1][1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int u = e[0]-1, v = e[1]-1;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        
        vector<vector<int>> dis(n, vector<int>(2, INT_MAX / 2));
        dis[0][0] = 0;
        deque<pair<int, int>> q;
        q.push_back({0, 0});
        while (!q.empty()) {
            int u = q.front().first, d = q.front().second;
            q.pop_front();
            int sw = d / change;
            int nd = sw & 1? (sw + 1) * change + time : d + time;
            for (int v : g[u]) {
                if (dis[v][0] > nd) {
                    dis[v][0] = nd;
                    q.push_back({v, nd});
                }
                else if (dis[v][0] < nd && dis[v][1] > nd) {
                    dis[v][1] = nd;
                    q.push_back({v, nd});
                }
            }
        }
        return dis[n-1][1];
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,
1 girl, solo, long hair, black hair, blue eyes, skirt, shirt, school uniform, standing, white shirt, short sleeves, pleated skirt, outdoors, sky, serafuku, (pink serafuku, pink school uniform), day, sailor collar, blurry, arm up, neckerchief, long skirt, girl