TopCoder

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

34.1% (14/41)

Description

角色扮演遊戲(RPG,英文全稱 Role-playing Game)是一種遊戲,在遊戲中,玩家扮演虛擬世界中的一個或者幾個隊員角色在特定場景下進行遊戲。角色根據不同的遊戲情節和統計數據(例如生命值、法力、力量、靈敏度、智力等等)具有不同的能力,而這些屬性會根據遊戲規則做對應的改變。 ---from Wikipedia

現在INFOR公司出了一款名叫皮皮歷險記的RPG遊戲,在這個虛擬世界中有著許多的皮皮洞窟而且裡面住著皮皮精,而每當到達一個皮皮洞窟時,你就可以和那裡的皮皮精進行決鬥,當你打敗他之後,你就可以繼續的前進。
想當然爾,你從一個皮皮洞窟到下一個皮皮洞窟時,就會遇到許多小怪(皮皮妖、皮皮蟲、皮皮鬼...),總之你必須要打掉許多小皮皮才能到達下個皮皮洞窟,而這期間你當然也是會升級(Level Up)的,因此你就可以增加你各項屬性值,以便打倒更強大的皮皮精。
而在遊戲最後,你將會到達一個叫皮皮神殿的地方(也是一個皮皮洞窟),那裡住著魔尊皮皮,也就是號稱史上最強的皮皮,你的最終目標就是打敗魔尊皮皮!!!!

為了打敗強大的皮皮,所以你決定買這個遊戲來闖關,但是你發現寒假快結束了,所以希望能以最少的時間來達成打敗魔尊皮皮的任務。

而INFOR公司為了不要讓玩家覺得打皮皮精太輕鬆,也不會覺得太困難,所以每到一個皮皮洞窟時,要打的皮皮等級會被設定成與當前你的等級相同。
不過話雖如此,因為你有狡猾詭譎糟糕邪惡的腦袋,所以一到達皮皮洞窟後,總是能把皮皮精秒殺,但是前提是,你打這個皮皮精的等級必須要高於打上一隻皮皮精的等級才行(除了打的第一隻皮皮精之外)。
還有就是同個皮皮洞窟是可以走超過一次的,因為皮皮精會吸收天地精華然後復活,並且變得更強大(跟超級賽亞人一樣),因此你每到一個皮皮洞窟就一定會跟皮皮精進入戰鬥,即使你曾經打敗過這個皮皮洞窟的皮皮精。
並且並不是任兩個皮皮洞窟都是連通的,也不是任兩個皮皮洞窟都只有一條路可以走,但是每條路都是雙向的。
一但開始走某條路後就不能回頭了,而且一定會花t單位的時間(不論你等級多少),而且一定會提升到p等(同樣不論你等級多少)。

現在你算出了從某個皮皮洞窟到下一個皮皮洞窟需要花多少的時間,與等級提高到多少等,還有一開始所在的皮皮洞窟與皮皮神殿的位置,請問你要到達皮皮神殿至少要花多少時間呢?(假設你一開始是-1等的)

Input Format

輸入包含一個皮皮歷險記的地圖。
首先有四數n與m,s,e(0<=n,m<=500000,1<=s,e<=n)。分別代表關鍵地點的數量,道路數量,起始位置,皮皮神殿位置。
接下來有m行,每行包含四個整數i,j,t,p(1<=i,j<=n,0<=t,p<=2147483647)。
代表有條連接關鍵地點i,j的道路,並且行經需要花t單位時間,等級也會提高到p等。

Output Format

輸出一數代表最少需要花多少時間才能破關破到打魔尊皮皮。
假如無論如何都無法到達的話,請輸出"Pipi how way!!!"

Sample Input

6 10 1 6
1 2 4 1
1 3 2 1
3 2 1 2
2 3 3 1
4 2 2 8
3 4 100 30
4 6 7 8
2 5 10 6
2 5 10 3
6 5 100 30

Sample Output

113

Hints

Problem Source

原TIOJ1530 / INFOR 22nd幹部考(prob G)。Idea:math120908

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5
5 900 65536 262144 6
6 900 65536 262144 7
7 900 65536 262144 8
8 900 65536 262144 9
9 900 65536 262144 10