森森旅游天梯賽題目中，Z省有n座城市和m條有向旅行線路，森森要從1號城市到n號城市旅游，每次經(jīng)過線路需支付費用，森森現(xiàn)金為q，旅行金為0，且能在一個城市用1個現(xiàn)金換k個旅行金，解題時可對1到n所有點建圖正向跑關(guān)于c的最短路，反向建圖對n到1所有點跑關(guān)于d的最短路，令正向最短路為dis1[i]，反向最短路為dis2[i]。

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

森森旅游 天梯賽

問題描述

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

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

解決方法

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

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

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

注意事項

在解決問題時，我們需要注意以下幾點：

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