Gửi email

Xem dưới dạng PDF
Gửi bài giải
Điểm: 10
Giới hạn thời gian: 3.0s
Giới hạn bộ nhớ: 256M
Tác giả:
ruby
Kiểu bài tập

Có \(n\) SMTP server kết nối với nhau bởi mạng có dây. Có \(m\) sợi cáp, mỗi sợi cáp nối 2 server và sẽ có độ trễ \(w\) để gửi email giữa 2 server đó.

Tính thời gian ngắn nhất để gửi email từ server \(S\) đến server \(T\) bởi mạng có dây trên là bao nhiêu?

Lưu ý: Các server được đánh số thứ tự từ \(0\) đến \(n-1\).

Input:

Dòng đầu tiên là số bộ test. Mỗi bộ test như sau:

  • Dòng đầu tiên của mỗi bộ test lần lượt là 4 số: \(n\), \(m\), \(S\), \(T\)
  • \(m\) dòng tiếp theo của mỗi bộ test mô tả các kết nối mạng và độ trễ: \(a\) \(b\) \(w\) cho biết có dây cáp nối giữa máy \(a\) và máy \(b\) và giữa 2 máy độ trễ là \(w\).

Output

  • Với mỗi bộ test, output trên 1 dòng số thứ tự bộ test "Case \(\#x\): " theo sau là thời gian cần thiết để gửi email từ \(S\) đến \(T\). Nếu không thể gửi được thì output "unreachable".

Constraints

  • \(2 \le n \le 20000\)
  • \(0 \le m \le 50000\)
  • \(0 \le S \lt n\)
  • \(0 \le T \lt n\)
  • \(S \ne T\)
  • \(0 \le w \le 10000\)

Example

Sample input

3
2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1

Sample output

Case #1: 100
Case #2: 150
Case #3: unreachable