尋找最短等待時間的路徑

Question

我正在從競爭中解決這個問題。我會在這裏簡要描述這個問題。

一位廚師正試圖在時間T之前到達會議場所，但他希望在巴士站儘量減少等待時間。除非他在T之前到達目的地，並且在巴士站等候最少，否則他並不介意走長路線。他從第一站開始，目的地是最後一站。這裏是輸入規範...

N T M 
U V S E 
U V S E 
... and so on 

其中N是站數，T是會議時間，M是總線數。接下來的M線是巴士細節。 U是公共汽車開始的地方，V是它到達的地方。 S是開始時間，E是到達時間。所以公共汽車開始在車站，U在時刻S，在時間到達工位V E.

Constraints 
2 ≤ N ≤ 50000 
1 ≤ T ≤ 109 
1 ≤ M ≤ 100000 (105) 
1 ≤ U ≤ N 
1 ≤ V ≤ N 
U ≠ V 
0 ≤ S < E ≤ 10 

這是我已經試過了，代碼後，並在代碼解釋如下。

public int findMax(int nextStation, int rcd, int start, int end) { 
    int tt = start - rcd; 
    // If we reached destinaion, i.e the last station 
    // no more wait has to be done and we return the time 
    // required to reach here 
    if (nextStation == noOfStations) { 
     return tt; 
    } 

    // TODO : we already found a better path, so we skip this one 
    // if (tt > minTillNow) { 
    // return Integer.MAX_VALUE; 
    // } 

    List<Bus> buses = stations.get(nextStation); 

    // If we have not reached finalStation 
    // and there are no more buses from this station, 
    // we reached a dead end. 
    if (buses == null) { 
     return -1; 
    } 

    int temp, min = Integer.MAX_VALUE; 
    // If there are buses from this station, we try all 
    // of them 
    for (int i = 0; i < buses.size(); i++) { 
     temp = findMax(buses.get(i).v, end, buses.get(i).s, buses.get(i).e); 
     // Find minimum wait-time 
     if (temp != -1 && temp < min) { 
      min = temp; 
     } 
    } 
    // If no subtree has a path 
    if (min == Integer.MAX_VALUE) return -1; 
    // if the wait to reach here is greater than any subsequent 
    else if (min < tt) return tt; 
    else 
     return min; 
} 

我做了DFS，開始在第一站，並找到最長等待時間沿任意路徑，直到結束，然後選擇最低的所有等待沿着這樣的路徑倍。這對於給定的輸入示例很好。

Input: 
5 10 5 
1 2 1 2 
1 5 3 4 
2 4 4 5 
2 5 5 6 
4 5 6 7 

Output: 
2 

但我失敗時，我提交了一些測試輸入，與「錯誤的答案」。 有人可以發現上述方法的問題嗎？這也是一個很好的方法嗎？這會是什麼複雜性？我認爲它應該是M的線性，是正確的近似值。

Answer 1

我想你忘記的是測試你是否仍然可以在for循環中捕捉總線（如下面的示例所示）。

除此之外，我認爲你的代碼比需要的更復雜。首先，編碼-1的「無路徑」不是很方便，因爲在評估最小等待時間時需要額外的測試（我假設如果沒有路徑，必須返回-1，但是您可以在結束）。

我會建議以下功能（並且引入了N和T的新名稱，但我認爲它們足夠有意義）。

public int minWaitingTime(int currentStop, int currentTime, int waitingTime) { 
    if (currentStop == destination) { 
     // reached the destination, return waitingTime if we met the deadline, 
     // or 'infinity' otherwise 
     // NOTE: I assumed currentTime <= deadline is ok, maybe that should be < 
     return currentTime <= deadline ? waitingTime : Integer.MAX_VALUE; 
    } else {   
     List<Bus> buses = stations.get(currentStop); 

     int min = Integer.MAX_VALUE; 
     for (Bus bus : buses) { 
      // test if we can still catch this bus 
      if (bus.s <= currentTime) { 
       // update minimum 
       min = Math.min(min, 
         minWaitingTime(bus.v, bus.e, 
          waitingTime + (bus.s - currentTime)); 
      } 
     } 

     return min; 
    } 
} 

你可能現在只是稱這個爲：

public int findMinWaitingTime() { 
    int min = minWaitingTime(1, 0, 0); 
    return min == Integer.MAX_VALUE ? -1 : min; 
} 

順便說一句，我希望這是一個古老的比賽，我現在不寫你的解決方案...

Answer 2

這看起來像Google Code Jam問題。您可以找到其他人在其網站上提供的解決方案。

使用深度優先搜索的問題在於它具有幾何增加的複雜性。因此，例如，如果您有10個站點和10個來自每個站點的連接，則有10^10個路徑在數十億之內。這就像試圖蠻力解決國際象棋。

這種問題可以通過動態編程來解決（Code Jam喜歡DP問題）。你知道這一點的原因是，在任何特定的電臺最好的行動是獨立於你以前曾經去過的電臺。從最後一個車站向後解決問題。您將始終能夠以這種方式找到任何特定移動的最短等待時間。

唯一的障礙是最小的等待時間路徑可能T.

以後抵達，因此，解決你應該做在最短等待尋路回溯搜索的問題。換句話說，您可以像以前一樣執行DP解決方案，但要記錄花費的總時間。如果它超過T，則返回到前一個節點並繼續從那裏搜索。

---

順便說一句，避免使用像「temp」和「i」這樣毫無意義的變量名，它會導致錯誤。