网上这么多大佬用 01 分数规划（完全不会），这里写一篇分层图造福社会。
前置芝士：最短路。
一个有向无环图，第一个想到的就是拓扑排序。
定义 \(dp(i)\) 为到达第 \(i\) 个点所需要的经过点数和边权和（一个 pair），正常转移即可。
然后就发现假了。
因为如果能够这样转移，就一定满足：
\[\frac{a}{x} \lt \frac{b}{y} \iff \frac{a + w}{x + 1} \lt \frac{b + w}{y + 1} (w \in \mathbb{N}) \]但显然它不成立。
考虑 dp 数组多开一维。
\(dp(i, j)\) 为第 \(i\) 个点，走到这需要走 \(j\) 步时的最小的代价（因为当 \(a\) 一定时只有 \(b\) 最小才能使得 \(\frac{b}{a}\) 最小）。
转移就显而易见了。
\[dp(i, j) = \min _ {k \in g_i} dp(k, j - 1) \]其中 \(g_i\) 表示图中所有能指向 \(i\) 的点的集合。
但此时我们就不能用拓扑排序，而需要用最短路（dijkstra 或者 SPFA 等）。
namespace zqh {
const int N = 205;
int n, m, dp[N][N], in[N];
vector<pii> g[N];
void dijkstra() {
p_q<pii, vector<pii>, greater<pii>> q;
memset(dp, 0x3f, sizeof(dp));
q.push({1, 1});
dp[1][1] = 0;
while (q.size()) {
int u = q.top().first, step = q.top().second;
q.pop();
for (auto [v, w] : g[u]) {
if (dp[v][step + 1] > dp[u][step] + w) {
dp[v][step + 1] = dp[u][step] + w;
q.push({v, step + 1});
}
}
}
}
void init() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
in[v]++;
}
}
void solve() {
dijkstra();
double ans = LLONG_MAX * 1.0;
for (int i = 1; i <= n; i++) {
ans = min(ans, (double)((double)(dp[n][i]) / (double)(i)));
}
cout << fixed << setprecision(3) << ans;
}
void main() {
init();
solve();
}
} // namespace zqh