Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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.
Sample Input
3 4
1 2 1
2 3 4
1 3 2
1 2 3
Sample Output
3
2
1 3
Bình luận