Submit　　Ranklist

Problem : 156 - Xor路徑和

Problem Statistics

Solved Member: 6　　Submission: 10　　User Tried: 6

Statement:

給你一張 n 個點 m 條雙向邊的圖，圖上每條邊有一個非負的權值。

你希望從 1 找一條到 n 的路徑，使得路徑上所有邊權 xor 起來是最大的。

Input:Output:

第一行有兩個數字 n,m，代表點數和邊數。
後面 m 行每行有三個數字 a,b,Di，代表a,b之間有一條權值Di的道路。
邊可能會有自環或者重邊的情況發生。

輸出一個數字，代表到 n 最大的權值。

Sample Input:Sample Output:

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

HINT:

如圖，路徑 1-2-4-3-5-2-4-5 對應的 XOR 和為 2 XOR 1 XOR 2 XOR 4 XOR 1 XOR 1 XOR 3=6
當然，一條邊數更少的路徑 1-3-5 對應的 XOR 和也是 2 XOR 4=6
【數據規模】
對於20%的數據，N<=100，M<=1000，Di<=10^4
對於50%的數據，N<=1000，M<=10000，Di<=10^18
對於70%的數據，N<=5000，M<=50000，Di<=10^18
對於100%的數據，N<=50000，M<=100000，Di<=10^18

Source:

WC 2011

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10