森森旅游 天梯賽：森森旅游天梯賽怎么算

森森旅游 天梯賽是一個(gè)關(guān)于旅行路線規(guī)劃的問(wèn)題,在這個(gè)問(wèn)題中，森森決定去Z省旅游，Z省有n座城市（從1到n編號(hào)）以及m條連接兩座城市的有向旅行線路,每次經(jīng)過(guò)一條旅行線路時(shí)都需要支付該線路的費(fèi)用，但這個(gè)收費(fèi)標(biāo)準(zhǔn)可能不止一種，例如車票跟機(jī)票一般不是一個(gè)價(jià)格,Z省為了鼓勵(lì)大家在省內(nèi)多逛逛，推出了旅游金計(jì)劃：在i號(hào)城市可以用1元現(xiàn)金兌換ai元旅游金（只要現(xiàn)金足夠，可以無(wú)限次兌換）,城市間的交通即可以使用現(xiàn)金支付路費(fèi)，也可以用旅游金支付,具體來(lái)說(shuō)，當(dāng)通過(guò)第j條旅行線路時(shí)，可以用cj元現(xiàn)金或dj元旅游金支付路費(fèi),對(duì)于不同的線路，旅客可以自由選擇不同的支付方式

森森旅游 天梯賽

問(wèn)題描述

森森旅游 天梯賽是一個(gè)關(guān)于旅行路線規(guī)劃的問(wèn)題。在這個(gè)問(wèn)題中，森森決定去Z省旅游，Z省有n座城市（從1到n編號(hào)）以及m條連接兩座城市的有向旅行線路。每次經(jīng)過(guò)一條旅行線路時(shí)都需要支付該線路的費(fèi)用，但這個(gè)收費(fèi)標(biāo)準(zhǔn)可能不止一種，例如車票跟機(jī)票一般不是一個(gè)價(jià)格。Z省為了鼓勵(lì)大家在省內(nèi)多逛逛，推出了旅游金計(jì)劃：在i號(hào)城市可以用1元現(xiàn)金兌換ai元旅游金（只要現(xiàn)金足夠，可以無(wú)限次兌換）。城市間的交通即可以使用現(xiàn)金支付路費(fèi)，也可以用旅游金支付。具體來(lái)說(shuō)，當(dāng)通過(guò)第j條旅行線路時(shí)，可以用cj元現(xiàn)金或dj元旅游金支付路費(fèi)。對(duì)于不同的線路，旅客可以自由選擇不同的支付方式。

森森決定從1號(hào)城市出發(fā)，到n號(hào)城市去。他打算在出發(fā)前準(zhǔn)備一些現(xiàn)金，并在途中的某個(gè)城市將剩余現(xiàn)金全部換成旅游金后繼續(xù)旅游，直到到達(dá)n號(hào)城市為止。Z省政府會(huì)根據(jù)每個(gè)城市參與活動(dòng)的情況調(diào)整匯率（即調(diào)整在某個(gè)城市1元現(xiàn)金能換多少旅游金）。現(xiàn)在需要幫助森森計(jì)算一下，在每次調(diào)整之后最少需要攜帶多少現(xiàn)金才能完成他的旅程。

解決方法

解決這個(gè)問(wèn)題的一種方法是使用Dijkstra算法。首先，我們需要建立一個(gè)圖，其中每個(gè)節(jié)點(diǎn)代表一個(gè)城市，每條邊代表一條旅行線路，邊的權(quán)重是該線路的費(fèi)用。然后，我們可以從1號(hào)城市開始，使用Dijkstra算法計(jì)算到達(dá)每個(gè)城市的最小費(fèi)用。在計(jì)算過(guò)程中，我們需要考慮到兩種支付方式：現(xiàn)金和旅游金，并選擇費(fèi)用最低的支付方式。同時(shí)，我們還需要記錄下在每個(gè)城市進(jìn)行旅游金兌換的最小現(xiàn)金量。

由于可能存在多個(gè)兌換點(diǎn)，所以我們需要考慮多種路徑和費(fèi)用。具體來(lái)說(shuō)，我們可以使用堆優(yōu)化版本的Dijkstra模板來(lái)解決這個(gè)問(wèn)題。在這個(gè)模板中，我們需要將dist數(shù)組初始化為long long類型，以存儲(chǔ)較大的數(shù)值。我們還需要使用multiset來(lái)維護(hù)每個(gè)城市的最小費(fèi)用。

在每次匯率調(diào)整之后，我們需要重新計(jì)算從1號(hào)城市到達(dá)每個(gè)城市的最小費(fèi)用，并輸出調(diào)整后的森森至少需要準(zhǔn)備多少現(xiàn)金，才能按他的計(jì)劃從1號(hào)城市旅行到n號(hào)城市。

注意事項(xiàng)

在解決問(wèn)題時(shí)，我們需要注意以下幾點(diǎn)：

• 每次只能選擇一種支付方式，不可同時(shí)使用現(xiàn)金和旅游金混合支付。
• 如果森森決定在途中的某個(gè)城市兌換旅游金，那么他必須將剩余現(xiàn)金全部、一次性兌換，剩下的旅途將完全使用旅游金支付。
• Z省政府會(huì)根據(jù)每個(gè)城市參與活動(dòng)的情況調(diào)整匯率，因此在旅程中，森森需要靈活應(yīng)對(duì)這些調(diào)整。