|
|
Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language
version or invalid test data, or description of the problem is not clear.
Từ tập các bài có trên SPOJ (acm)
941. Hai ðường ði
Mã bài: HIWAY
|
Một mạng giao thông gồm N nút giao thông, và có M ðường hai chiều nối một số cặp nút, thông tin về một ðường gồm ba số nguyên dương u, v là tên hai nút ðầu mút của ðường, và l là ðộ dài ðoạn ðường ðó. Biết rằng hai nút giao thông bất kì có không quá 1 ðường hai chiều nhận chúng làm hai ðầu mút.
Cho hai nút giao thông s và f, hãy tìm hai ðường ði nối giữa s với f sao cho hai trên hai ðường không có cạnh nào ðược ði qua hai lần và tổng ðộ dài 2 ðường ði là nhỏ nhất.
Input
- Dòng ðầu ghi N, M (N ≤ 100)
- Dòng thứ 2 ghi hai số s, f.
- M dòng tiếp theo, mỗi dòng mô tả một ðường gồm ba số nguyên dương u, v, l.
Output
- Dòng ðầu ghi T là tổng ðộ dài nhỏ nhất tìm ðược hoặc -1 nếu không tìm ðược.
- Nếu tìm ðược, hai dòng sau, mỗi dòng mô tả một ðường ði gồm: số ðầu là số nút trên ðường ði này, tiếp theo là dãy các nút trên ðường ði bắt ðầu từ s, kết thúc tại f.
Chú ý: Phạm vi tính toán trong vòng Longint.
Example
Input:
5 8
1 5
1 2 1
1 4 8
2 3 5
2 4 1
3 5 1
4 3 8
4 5 1
1 3 1
Output:
5
3 1 3 5
4 1 2 4 5
| Được gửi lên bởi: | Nguyen Dinh Tu |
| Ngày: | 2006-09-14 |
| Thời gian chạy: | 1s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO JS PERL 6 PYTH 3.1.2 SCALA SED TCL |
|
|
|
|
