Đường đi trung bình nhỏ nhất

Binary-search Buổi 13 — Chặt nhị phân đáp án Dynamic Programming
Points
42
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$.
Draft saved