經過了一連串的冒險, 終於救出了妁艷, 摧毀了邪惡組織的陰謀.
這時, 冥王星上除了妁艷, 妤嬌, 姊姊, 妹妹, 火姬之外, 沒有任何人了.
“葛格, 我們走吧! 回地球去吧!” 妁艷妹妹說.
“恩.., 好不容易來到冥王星的, 這樣就回去實在太可惜了.” 妁艷說.
“不做嗎?” 妁艷繼續說.
“我才沒有...” 妁艷妹妹紅著臉頭偏向一邊說.
“其實妳很想要對吧!? 看看妳的表情!?” 妁艷接著說.
“葛格, 但是你的微甲..., 啊啊啊, 不要♥ ”
“嘴巴上說不要, 身體倒是挺誠實的嘛!” 妁艷強拉著妹妹的手.
想不到妁艷妹妹竟然有在冥王星上散步的興趣.
兩人決定在返回地球前, 在冥王星上逛一圈.
為了不讓其他人等太久, 他們決定以最快的速度參觀一些冥王星上的風景然後返回原地.
但是參觀重複的地方實在太無聊了, 他們決定不經過重複的地方或道路.
“啊, 好刺激, 再這樣下去的話我會~~~♥ ” 妁艷妹妹表示其對路上風景的看法.
“平時看起來很乖巧的, 在這種時候果然很變態呢!” 妁艷說.
冥王星上有許多景點, 包含原出發點. 同時, 有許多道路連接於景點之間, 兩景點最多有一條路連接.
一條道路可能是在坡道上, 所以兩個方向行進的時間可能不同.
為了不讓妁艷妹妹壞掉, 保證冥王星上存在一條路徑不經過重複的道路或景點, 並返回出發點.
第一行有兩個正整數n, m, 代表有幾個景點幾條道路, 其中第1個景點為出發點.
接下來有m行, 每行有四個正整數a, b, c, d, 其中a ≠ b. 分別代表有條道路連接第a, b兩景點, 而從a到b要花c單位的時間, 從b到a要花d單位的時間.
對30%的測資n ≤ 50
對60%的測資n ≤ 3,000, m ≤ 5,000
對100%的測資n ≤ 5,000, m ≤ 10,000, 1 ≤ c, d ≤ 10,000
輸出一個數字, 以最快的速度參觀冥王星上的一些風景然後返回原地需要多久.
原TIOJ1793 / problem setter: willyliu; source: POI XI The Competition
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 |