燃料限制的最短路徑

我在競賽的某個地方發現了這個問題，但尚未能夠提出解決方案。我正在考慮應用迪克斯特拉的東西，但它不是很清楚：燃料限制的最短路徑

''您會得到一個城市加權連接圖，所有邊都有正的權重。一些城市（節點）有加油泵，而有些則沒有。你有一輛容量爲C的自行車。也就是說，在裝滿油箱的情況下，汽車可以行駛C個單位的距離。在任何有加油泵的城市，汽車都可以充滿油箱。找出給定源和給定目的地之間的最短路徑。假設你從一個滿罐開始。''

我有一種感覺O（mn logn）會被它接受。

來源

2014-02-27 therealone

什麼是數據範圍是多少？ –

前段時間我曾看過這個問題，所以我不記得範圍。我對O（mn logn）的感覺是當我第一次看到這個問題的時候。請隨時提出具有不同時間複雜性的解決方案。我沒有任何東西。 :) – therealone

非常實際的電動汽車;-) –

基本上你需要根據自行車到達時的剩餘燃料將每個節點n_i分割成多個節點，我們稱之爲（n_i，r）。你不需要在開始時創建所有（n_i，r），你可以在飛行中完成。

然後類似於Dijkstra，你從節點（n_0，C）開始，每次你可以找到下一個（n_x，r）時可以用最小的距離到達。並更新連接到（n_x，r）的所有節點（n_y，ry）。如果n_y有泵，ry將重置爲C.如果對於n_y，已經有一個節點（n_y，r）和r> = ry，那麼您不需要創建新節點（n_y，ry），只需忽略它。

我不能說運行時間的複雜性，但它應該足以在比賽中獲得AC。

來源

2014-02-27 07:19:08

哪個節點應該在（n_0，C）之後選擇？我想你需要在每個節點上存儲（distanceTravelled，n_i，r），並且每次都選擇距離最近的節點。複雜性將是（no_of_nodes *容量）日誌（no_of_nodes *容量） – cegprakash

@蒂姆格林的方法將創建一個指數（在加油站的數量）節點的數量。運行迪克斯特拉的話會很慢。有一個更快的方法。

首先，找出所有加油站之間的距離。還包括從源到每個加油站，從每個加油站到完成，從源到完成的距離。這可以通過多次運行Dijkstra's來完成。

這將爲您提供從開始到結束的所有可能的有效路線圖。只需在此圖上再次運行Dijktra就可以獲得最終解決方案。

由於Dijkstra的每次運行將Ô（V ）（V =城市的數量）並且必須運行它O（G）倍（G =加油站的次數， Djikstra的一次運行可以找到從一個加油站到所有其他加油站的距離），該算法將運行在O（V G）時間。

來源

2014-02-27 17:34:46

+1。雖然如果圖表很稀疏但有許多加油站，但對所有對最短路徑使用[約翰遜算法]（http://en.wikipedia.org/wiki/Johnson%27s_algorithm）可能會更好。 – Nuclearman

你不必在所有的加油站之間找到距離，看到我的答案... –

@PavelGatnar：找到所有加油站之間的距離是哎呀（V^2 * G）**。一旦我考慮到這一點，我的答案仍然與您的答案一樣複雜（儘管您的練習在實踐中會稍微快一點）。做得好！ –

Dijkstra算法存在一個修改，即加油站頂點之間的距離是根據需要通過另一個Dijkstra算法修改計算的，該算法在指定範圍內搜索所有未解決的加油站頂點。

把手開始和完成爲加油站。
將開始放入主優先隊列。
運行主Dijkstra與子Dijkstra。

主迪傑斯特拉執行在一個循環中執行以下步驟：當所述主優先級隊列爲空了「完成不可達」
0退出。
1.將加油站從主優先隊列中取出。
2.完成時退出。
3.呼叫子Dijkstra提供未解決的鄰居加油站距離實際的距離。

子Dijkstra算法使用自己的優先級隊列中搜索燃料範圍內的實際加油站所有頂點的最短路徑（直到隊列爲空）和手柄根據他們的狀態達到加油站：
*已經解決了主 - 不要處理傳出邊緣。
*等候在主隊列 - 更新距離（當低則decreaseKey）和路徑
*否則把它放到主隊列

來源

2016-01-15 00:09:21

燃料限制的最短路徑

回答

相關問題