Chu Trình Có Hướng Trọng Số Nhỏ Nhất
Points
80
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một đồ thị có hướng có trọng số gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cung có hướng. Mỗi cung đi từ $u_i$ đến $v_i$ ($u_i \ne v_i$) có trọng số nguyên dương $w_i$. Có thể tồn tại nhiều cung nối cùng một cặp đỉnh theo cùng một hướng.
Hãy tìm tổng trọng số nhỏ nhất của một chu trình có hướng bất kỳ trong đồ thị (gồm ít nhất $2$ cung). Nếu đồ thị không chứa chu trình nào, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($2 \le N \le 300$, $0 \le M \le 5000$).
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le w_i \le 10^9$).
Dữ liệu ra
In ra tổng trọng số nhỏ nhất của một chu trình có hướng, hoặc -1 nếu không tồn tại chu trình.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 4 2 3 5 3 1 2 2 4 1 4 1 3 |
8 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion