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à ~m_1~,~m_2~,…,~m_k~ thì trọng số của đường đi này là ~m_1~ or ~m_2~ or … ~m_k~

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
3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3
output
3

Giới hạn:

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

Comments

Please read the guidelines before commenting.