#P7993. [2021年山东省队集训]图论题

    ID: 8006 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2100提高+/省选-Dijkstra反图求到终点距离Li Chao 线段树

[2021年山东省队集训]图论题

题目描述

给定一个 nn 个节点,mm 条有权边的有向图,第 ii 条边的边权是 wiw_i,从 uiu_i 到 viv_i, Reimu 从 ss 点出发,目标是到 tt 点找 Satori。

Reimu 想尽快到达 tt 点,所以她让 Yukari Yakumo 帮助她,有一个技能是可以对任意两个点 x,yx,y,新建一条 xx 到 yy 的边,边权为 (x−y)2(x-y)^2,这个技能只能使用一次。

求 ss 到 tt 的最小时间?

输入格式

第一行四个数表示 n,m,s,tn,m,s,t。

之后 mm 行,每行三个数 u,v,wu,v,w 表示原有的一条边,保证无重边。

输出格式

一行一个数表示答案。

样例 #1

样例输入 #1

5 6 1 5
1 2 3
1 3 5
2 3 1
3 4 10
4 5 1
3 5 8

样例输出 #1

6

提示

Reimu 可以从 11 走到 22,然后从 22 走到 33,用时为 3+1=43+1=4,然后用技能建立 3,43,4 之间的边,代价为 (3−4)2=1(3-4)^2=1,于是走到 44 用时为 4+1=54+1=5,然后走到 55 用时为 5+1=65+1=6。

数据范围

本题采用子任务评测。

对于 20%20\% 的数据,满足 1≤n≤51\leq n\leq 5 且 1≤m≤101\leq m\leq 10。

对于 40%40\% 的数据,满足 1≤n≤1001\leq n\leq 100 且 1≤m≤3001\leq m\leq 300。

对于 60%60\% 的数据,满足 1≤n≤20001\leq n\leq 2000 且 1≤m≤100001\leq m\leq 10000。

对于 100%100\% 的数据,满足 1≤s,t≤n≤2×1051\leq s, t\leq n\leq 2\times 10^5, 0≤m≤4×1050\leq m\leq 4\times 10^5,1≤w≤1091\leq w\leq 10^9。