1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!

Problem 1005. -- 【2012四川省热身赛】Problem C. OR Shortest Path

1005: 【2012四川省热身赛】Problem C. OR Shortest Path

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 0
[Submit][Status][Web Board]

Description

OR is a kind of bitwise operator, we defined that as follow: for two number A and B in binar notation, let C = A OR B. Then for each bit of C, we can get its value by check the digit of corresponding position in A and B. For each digit, 1 OR 1 = 1, 1 OR 0 = 1, 0 OR 1 = 1, 0 OR 0 = 0. And we simply write this operator as |, like 2 | 1 = 3, 2 | 3 = 3.In bitland there is a strange method to calculate the length of a path using OR. If there are M
edges in a path, and the length of them are l1; l2; · · · ; lM, then the length of this path is l1 | l | · · · | lM. Now give you a undirected graph with N nodes and M edges, find the OR shortes path between S and T. If S and T are disconnect, we consider the length between them is −1.

Input

First line of the input is a single integer T(T ≤ 30), indicates there are T test cases.
For each test case, the first line is four integers N(2 ≤ N ≤ 104), M(1 ≤ M ≤ 105), S,T(1 ≤ S; T ≤ N; S ̸= T), indicates the number of nodes, the number of egdes, the startingnode and the target node respectively. Following M lines, each line contains three integers a bc(1 ≤ a; b ≤ N, a ̸= b, 0 ≤ c < 230), means there exist an undirected edge between node a and node b, and the length is c.

Output

For each test case, output one line. First ,output “Case #t: ”, where t is the number of test case,
from 1 to T. Then, you should output a single line contains a single number means the length of
the OR shortest path between S and T or −1.

Sample Input

3
4 4 1 4
1 2 1
1 3 2
2 4 2
3 4 1
4 4 1 4
1 2 6
1 3 2
2 4 2
3 4 5
4 2 1 4
1 2 4
3 4 5

Sample Output

Case #1: 3
Case #2: 6
Case #3: -1

HINT

Source

[Submit][Status][Web Board]