Đường đi trung bình nhỏ nhất
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh đánh số từ $1$ đến $N$ và $M$ cạnh có hướng. Cạnh thứ $i$ đi từ $u_i$ đến $v_i$ ($u_i < v_i$) với trọng số $w_i$.
Với một đường đi từ đỉnh $1$ đến đỉnh $N$ đi qua $k$ cạnh ($k \ge 1$) có tổng trọng số là $S$, trọng số trung bình của đường đi đó là $\frac{S}{k}$. Hãy tìm trọng số trung bình nhỏ nhất trong tất cả các đường đi từ $1$ đến $N$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
- $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$.
Dữ liệu ra
In ra trọng số trung bình nhỏ nhất tìm được với đúng $6$ chữ số sau dấu thập phân. Dữ liệu đảm bảo luôn có ít nhất một đường đi từ $1$ đến $N$.
Ví dụ
| Input | Output |
|---|---|
| 4 4 |
1 2 4 2 4 2 1 3 10 3 4 1 | 3.000000 | | 3 2 1 2 5 2 3 8 | 6.500000 |
Giới hạn
- $2 \le N \le 10^4$
- $1 \le M \le 5 \cdot 10^4$
- $1 \le u_i < v_i \le N$
- $-10^6 \le w_i \le 10^6$.
Community Discussion