Chu Trình Có Hướng Trọng Số Nhỏ Nhất

Algorithms Buổi 52 — Mock Contest Phase 2 Graphs
Points
80
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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.

Draft saved