夜深人靜的夜晚,夜幕中掛著一絲新月。ericxiao
穿著華麗的禮服站在魔鏡前喃喃:
「魔鏡呀魔鏡!請問這世界上,最毒的人是誰?」
魔鏡不假思索的回答了
「偉大的ericxiao
呀,於東南外的扶餘國,住著一個人叫做ZCK
,他出的題目和方法極其毒,他就是世界上最毒的人!」
「是嗎?告訴我要怎麼去吧~」
「我沒有辦法告訴你,不過你的寶劍可以。」
ericxiao
不知道從哪裏抽出了一把寶劍,撫摸著它,彷彿在彈琴的問道:
「劍啊劍啊!我們回去吧!回到最毒的地方,與ZCK
一決勝負吧!我已決定用名為《懶得想題嘍》的毒蘋果將他毒死了!」
奇蹟似的,劍回應了,以只有ericxiao
看得懂的語言:
「Gefðu þér línurit yfir $ N $ stig, $ M $ brúnir, og upphafs- og lokapunkta $ s $ og $ t $, og hver brún hefur tvö brúnþyngd $ x $ og $ y $. Nú, hver er stysta leiðin sem þú vilt frá $ s $ til $ t $ (summan af $ y $ gildum allra hliða slóðarinnar)? Hins vegar verður að vera tryggt að XOR summan af $ x $ gildi brúnanna sem fara framhjá sé $ 0 $, og að brúnin sem er ítrekað gengið, verður að reikna brúnþyngd ítrekað. Ef ekki er hægt að uppfylla kröfurnar, vinsamlegast framleiðið -1
」
對於看不懂ericxiao
語的人們,中文則是:
「給定一個$ N $點,$M$個邊的無向圖,和起點終點$s$和$t$,而每一個邊都有兩個邊權$x$和$y$。現在呢,請問你要從$s$到$t$的最短路徑(路徑所有邊的$y$值相加)為何?不過呢,必須要保證走過的那些邊的$x$值XOR和為$0$,且重複走到的邊,邊權要重複算。若不存在滿足條件的路徑,則請輸出-1
。」
來幫助ericxiao
毒死毒瘤吧~
輸入第一行為$N,M,s,t$,依序代表點數、邊數、起點、訖點。接下來是$M$行,每一行格式為$a, b, x, y$,代表$a$,$b$之間有邊,和其$x$,$y$值。
對於所有的輸入,保證:
請輸出一個數字,代表答案。
OJDL 7092
Problem by Sean Liu
2020. 7. 8
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~4, 19 | $N \leq 10$ | 5 |
2 | 5~9 | $\forall x, x = 0$ | 10 |
3 | 10~14 | $M = N - 1$且圖連通 | 15 |
4 | 0~19 | 無其他限制 | 70 |