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.|

HIWAY - Hai đường đi

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/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
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2019-12-05 04:05:29


Last edit: 2019-12-05 04:05:46
2015-09-03 11:40:36 Anh chỉ yêu mình em ....LTKC
sao sai test cuối @@
2014-12-26 16:20:22 Ðức Anh
Lấy code MINCOST sửa tý nộp phát AC luôn :>
2014-09-05 17:16:24 Thcs Ðặng Chánh Kỷ
Ac, kết thúc phần luồng
2013-12-10 03:40:04 Xiao Lang
Kết quả sai. Chưa hiểu cái đoạn không có đường đi nào xuất hiện 2 lần trên 2 đường tìm được. Ví dụ như trong test đề bài đường đi 1->3,3->5 thì đường số 2 sẽ không có cạnh (1,3)~(3,1)~(3,5)~(5,3) nữa hay sao? Ai biết giải thích phát
2012-11-23 11:53:51 Nguyễn Tấn Phát
k
2012-08-15 17:43:23 Lê Trường Giang
Cho hỏi m <= ??
2012-04-03 08:18:19 Hoài Nam
co ai bit lam chi em voi
2011-07-17 17:51:29 NTQ
@Long BJ: Kệ cm a, xoắn à =))
2011-07-14 03:36:32 Le Viet Thanh Long
La loi signal =))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.