TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (23/23)

Submission's AC Ratio

62.1% (59/95)

Tags

Description

夜深人靜的夜晚,夜幕中掛著一絲新月。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毒死毒瘤吧~

Input Format

輸入第一行為$N,M,s,t$,依序代表點數、邊數、起點、訖點。接下來是$M$行,每一行格式為$a, b, x, y$,代表$a$,$b$之間有邊,和其$x$,$y$值。

對於所有的輸入,保證:

  • $1 \leq N \leq 1000$
  • $1 \leq a, b \leq N$ (可能會有重邊哦哦)
  • $1 \leq M \leq 5000$
  • $0 \leq x < 1024$
  • $0 < y \leq 1000000000 $

Output Format

請輸出一個數字,代表答案。

Sample Input 1

第一筆測資:
6 4 1 4
1 2 514 1
1 4 189 2
2 4 514 3
5 6 373 4
第二筆測資:
3 2 2 3
1 2 214 7122
1 3 244 8765
第三筆測資:
5 5 1 2
3 2 9 1
1 2 7 1
3 4 1 1
4 5 2 1
5 3 4 1

Sample Output 1

答案分別為:
4
-1
6

Hints

Problem Source

OJDL 7092
Problem by Sean Liu
2020. 7. 8

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 4
1 2000 65536 65536 1 4
2 2000 65536 65536 1 4
3 2000 65536 65536 1 4
4 2000 65536 65536 1 4
5 2000 262144 65536 2 4
6 2000 262144 65536 2 4
7 2000 524288 65536 2 4
8 2000 524288 65536 2 4
9 2000 524288 65536 2 4
10 2000 524288 65536 3 4
11 2000 524288 65536 3 4
12 2000 524288 65536 3 4
13 2000 524288 65536 3 4
14 3000 524288 65536 3 4
15 3000 524288 65536 4
16 3000 524288 65536 4
17 3000 524288 65536 4
18 3000 524288 65536 4
19 1000 65536 65536 1 4