Bitwise OR with Graph

View as PDF
Submit solution
Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout
Author:
admin
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho đồ thị có n đỉnh và m cạnh, các đỉnh được đánh số từ 1 đến n. Trên mỗi cạnh được gán một số nguyên không âm là trọng số của cạnh đó. Trọng số của một đường đi được tính bằng phép toán or (ký hiệu: or trong pascal, | trong C++), Nói cách khác, một đường đi qua các cạnh có trọng số lần lượt là m1,m2,…,mk thì trọng số của đường đi này là m1 or m2 or … mk

Cho đồ thị và 2 đỉnh s,t, hãy tìm đường đi có trọng số nhỏ nhất từ s đến t, nếu không tìm được đường đi thì in −1.

Dữ liệu vào:

  • Dòng đầu tiên ghi 2 số nguyên n,m
  • m dòng tiếp theo, mỗi dòng ghi 3 số nguyên u,v,c (1≤u,v≤n) cho biết c là trọng số của cạnh u,v
  • Dòng cuối cùng ghi 2 số nguyên s,t (1≤s,t≤n;s≠t)

Kết quả: Một số nguyên duy nhất là kết quả bài toán.

Ví dụ:
Input
Copy
3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3
output
Copy
3

Giới hạn:

  • 1≤n≤1000
  • 1≤m≤10000
  • 1≤c<1024

Comments

Please read the guidelines before commenting.