P9504 『MGOI』Simple Round I | C. 魔法禁林

题目背景

> 战斗的意义是为了生存,在这个竞争激烈的世界里,只有不断变强才能得以生存。——殿堂魔法士 S

题目描述

开学的第一天,小 M 迫不及待地计划着前往神秘的禁林。 小 M 拥有两个重要的属性,魔力值和生命值。非常特别的是,初始时,这两个值可以由小 M **任意决定**。 禁林可以看作一张 $n$ 个点 $m$ 条边的无向简单连通图。小 M 将在禁林里面行走,从起点 $s$ 走到 $t$。 每经过一条边,小 M 的**魔力值**都会减去 1。同时,每条边上有一个具有攻击力属性的魔兽,小 M 要与之战斗。若小 M 经过这条边之前的魔力值为 $k$,这条边上魔兽的攻击力为 $w$,那么经过这条边时发生的战斗将会消耗 $\left\lfloor \dfrac{w}{k} \right\rfloor$ 的**生命值**。魔兽不会被打败,因此**多次经过同一条边,每次都会发生战斗**。 **小 M 需要保证,当他的魔力值消耗完时,他的生命值为 0,且此时走到 $t$ 点。** 你需要求出小 M 初始时需要的最小生命值。

输入格式

输出格式

说明/提示

**【样例 1 解释】** 初始时,小 M 选择魔力值为 $2$,生命值为 $4$。 - $1\rightarrow2$:魔力值剩余 $1$,生命值剩余 $4 - \left\lfloor \frac{2}{2} \right\rfloor=3$。 - $2\rightarrow3$:魔力值剩余 $0$,生命值剩余 $3 - \left\lfloor \frac{3}{1} \right\rfloor=0$。 可以证明 $4$ 为小 M 初始时需要的最小生命值。 **【数据范围】** **本题采用 Subtask 捆绑测试。** 对于所有数据,$1 \le n \le 20000$,$1 \le m \le 40000$,$1\le s,t,u,v\le n$,$s\ne t$,图为无向简单连通图,$0\le w\le 100$。 | Subtask | $n$ | $m$ | $w\le$ | 分值 | | :------------: | :----------: | :----------: | :-----------: | :----------------:| | $1$ | $5$ | $10$ | $10$ | $11$ | | $2$ | $2000$ | $4000$ | $10$ | $27$ | | $3$ | $20000$ | $40000$ | $1$ | $19$ | | $4$ | $20000$ | $40000$ | $100$ | $43$ |