|
|
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)
1273. Mạng 3 ðỉnh
Mã bài: THREE
|
Cho một ða ðồ thị vô hướng N ðỉnh, M cạnh, mỗi cạnh có 1 trọng số nguyên dương.
Yêu cầu: Hãy chọn ra một số cạnh sao cho ðồ thị tạo bởi N ðỉnh và các cạnh ðược chọn này ðảm bảo liên thông giữa 3 ðỉnh 1, 2, 3 và tổng trọng số của các cạnh ðược chọn là nhỏ nhất. Dữ liệu vào ðảm bảo có phương án.
Giới hạn
- 3 ≤ N ≤ 100
- 4 ≤ M ≤ 20000
- Trọng số 1 cạnh ≤ 10000
Input
- Dòng ðầu tiên gồm 2 số nguyên: N, M.
- M dòng tiếp theo: dòng thứ i gồm 3 số nguyên dương U V C tương ứng là cạnh này nối liền ðỉnh U với ðỉnh V, trọng số là C.
Output
- Dòng 1: Chi phí nhỏ nhất.
- Dòng 2: Số nguyên K là số cạnh chọn ra.
- Ghi ra K số là chỉ số các cạnh ðã chọn, các số ghi cách nhau ít nhất một dấu cách.
Example
Input:
3 4
1 2 1
2 3 4
1 3 2
1 2 3
Output:
3
2
1 3
| Được gửi lên bởi: | Nguyen Minh Hieu |
| Ngày: | 2007-01-24 |
| Thời gian chạy: | 1s
|
| Giới hạn mã nguồn: | 10000B |
| 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 |
|
|
|
|
