U169078 [NOI2021SDPT3Test4]图论题

给定一个 $n$ 个节点，$m$ 条有权边的有向图，第 $i$ 条边的边权是 $w_i$，从 $u_i$ 到 $v_i$， Reimu 从 $s$ 点出发，目标是到 $t$ 点找 Satori。 Reimu 想尽快到达 $t$ 点，所以她让 Yukari Yakumo 帮助她，有一个技能是可以对任意两个点 $x,y$，新建一条 $x$ 到 $y$ 的边，边权为 $(x-y)^2$，这个技能只能使用一次。 求 $s$ 到 $t$ 的最小时间？

第一行四个数表示 $n,m,s,t$。 之后 $m$ 行，每行三个数 $u,v,w$ 表示原有的一条边，保证无重边。

一行一个数表示答案。

Reimu 可以从 $1$ 走到 $2$，然后从 $2$ 走到 $3$，用时为 $3+1=4$，然后用技能建立 $3,4$ 之间的边，代价为 $(3-4)^2=1$，于是走到 $4$ 用时为 $4+1=5$，然后走到 $5$ 用时为 $5+1=6$。 **数据范围** 本题采用子任务评测。 对于 $20\%$ 的数据，满足 $1\leq n\leq 5$ 且 $1\leq m\leq 10$。 对于 $40\%$ 的数据，满足 $1\leq n\leq 100$ 且 $1\leq m\leq 300$。 对于 $60\%$ 的数据，满足 $1\leq n\leq 2000$ 且 $1\leq m\leq 10000$。 对于 $100\%$ 的数据，满足 $1\leq s, t\leq n\leq 2\times 10^5$, $0\leq m\leq 4\times 10^5$，$1\leq w\leq 10^9$。