{"problem":{"name":"『MGOI』Simple Round I | C. 魔法禁林","description":{"content":"开学的第一天，小 M 迫不及待地计划着前往神秘的禁林。 小 M 拥有两个重要的属性，魔力值和生命值。非常特别的是，初始时，这两个值可以由小 M **任意决定**。 禁林可以看作一张 $n$ 个点 $m$ 条边的无向简单连通图。小 M 将在禁林里面行走，从起点 $s$ 走到 $t$。 每经过一条边，小 M 的**魔力值**都会减去 1。同时，每条边上有一个具有攻击力属性的魔兽，小 M 要与之战","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9504"},"statements":[{"statement_type":"Markdown","content":"开学的第一天，小 M 迫不及待地计划着前往神秘的禁林。\n\n小 M 拥有两个重要的属性，魔力值和生命值。非常特别的是，初始时，这两个值可以由小 M **任意决定**。\n\n禁林可以看作一张 $n$ 个点 $m$ 条边的无向简单连通图。小 M 将在禁林里面行走，从起点 $s$ 走到 $t$。\n\n每经过一条边，小 M 的**魔力值**都会减去 1。同时，每条边上有一个具有攻击力属性的魔兽，小 M 要与之战斗。若小 M 经过这条边之前的魔力值为 $k$，这条边上魔兽的攻击力为 $w$，那么经过这条边时发生的战斗将会消耗 $\\left\\lfloor \\dfrac{w}{k} \\right\\rfloor$ 的**生命值**。魔兽不会被打败，因此**多次经过同一条边，每次都会发生战斗**。\n\n**小 M 需要保证，当他的魔力值消耗完时，他的生命值为 0，且此时走到 $t$ 点。**\n\n你需要求出小 M 初始时需要的最小生命值。\n\n## Input\n\n第一行四个整数 $n,m,s,t$。\n\n接下来 $m$ 行，每行三个整数 $u,v,w$，表示编号为 $u\n,v$ 的点之间有一条边，边上魔兽的攻击力为 $w$。\n\n## Output\n\n一行一个整数，表示小 M 初始时需要的最小生命值。\n\n[samples]\n\n## Background\n\n> 战斗的意义是为了生存，在这个竞争激烈的世界里，只有不断变强才能得以生存。——殿堂魔法士 S\n\n## Note\n\n**【样例 1 解释】**\n\n初始时，小 M 选择魔力值为 $2$，生命值为 $4$。\n\n- $1\\rightarrow2$：魔力值剩余 $1$，生命值剩余 $4 - \\left\\lfloor \\frac{2}{2} \\right\\rfloor=3$。\n- $2\\rightarrow3$：魔力值剩余 $0$，生命值剩余 $3 - \\left\\lfloor \\frac{3}{1} \\right\\rfloor=0$。\n\n可以证明 $4$ 为小 M 初始时需要的最小生命值。\n\n**【数据范围】** \n\n**本题采用 Subtask 捆绑测试。**\n\n对于所有数据，$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$。\n\n| Subtask | $n$ | $m$ | $w\\le$ | 分值 |\n| :------------: | :----------: | :----------: | :-----------: | :----------------:|\n| $1$ | $5$ | $10$ | $10$ | $11$ |\n| $2$ | $2000$ | $4000$ | $10$ | $27$ |\n| $3$ | $20000$ | $40000$ | $1$ | $19$ |\n| $4$ | $20000$ | $40000$ | $100$ | $43$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9504","tags":["图论","洛谷原创","O2优化","记忆化搜索"],"sample_group":[["3 3 1 3\n1 2 2\n1 3 5\n3 2 3","4"],["5 10 1 5\n2 1 3\n3 1 7\n4 2 4\n5 3 9\n5 1 7\n2 3 2\n5 4 6\n1 4 10\n5 2 5\n3 4 10","6"]],"created_at":"2026-03-03 11:09:25"}}