308233: CF1486E. Paired Payment

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Paired Payment

题意翻译

给定图 $G=\lang V,E\rang$(不一定保证 $G$ 是一个连通图),请你找到从 $1$ 开始到达任意一个点 $t(t\in [1,n])$ 的最短路长度。 但是每次你不能只走 $E$ 中的一条边,而是选择两条边 $e_1,e_2\in E\;\text{s.t.}\;e_1=\lang x,u,w_1\rang,e_2=\lang u,y,w_2\rang$,然后,执行 $x\overset{e_1}\rightarrow u\overset{e_2}\rightarrow y$ 且每次走的花费是 $(w_1+w_2)^2$. 保证 $|V|\le 10^5,|E|\le \min\left\{2\times 10^5,{|V|\times (|V|-1)\over 2}\right\},\forall e=\lang u,v,w\rang \in E,w\le 50$.

题目描述

There are $ n $ cities and $ m $ bidirectional roads in the country. The roads in the country form an undirected weighted graph. The graph is not guaranteed to be connected. Each road has it's own parameter $ w $ . You can travel through the roads, but the government made a new law: you can only go through two roads at a time (go from city $ a $ to city $ b $ and then from city $ b $ to city $ c $ ) and you will have to pay $ (w_{ab} + w_{bc})^2 $ money to go through those roads. Find out whether it is possible to travel from city $ 1 $ to every other city $ t $ and what's the minimum amount of money you need to get from $ 1 $ to $ t $ .

输入输出格式

输入格式


First line contains two integers $ n $ , $ m $ ( $ 2 \leq n \leq 10^5 $ , $ 1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5) $ ). Next $ m $ lines each contain three integers $ v_i $ , $ u_i $ , $ w_i $ ( $ 1 \leq v_i, u_i \leq n $ , $ 1 \leq w_i \leq 50 $ , $ u_i \neq v_i $ ). It's guaranteed that there are no multiple edges, i.e. for any edge $ (u_i, v_i) $ there are no other edges $ (u_i, v_i) $ or $ (v_i, u_i) $ .

输出格式


For every city $ t $ print one integer. If there is no correct path between $ 1 $ and $ t $ output $ -1 $ . Otherwise print out the minimum amount of money needed to travel from $ 1 $ to $ t $ .

输入输出样例

输入样例 #1

5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2

输出样例 #1

0 98 49 25 114

输入样例 #2

3 2
1 2 1
2 3 2

输出样例 #2

0 -1 9

说明

The graph in the first example looks like this. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1486E/d05a9b1774a0eade44485bb99ef938693d1a95f9.png) In the second example the path from $ 1 $ to $ 3 $ goes through $ 2 $ , so the resulting payment is $ (1 + 2)^2 = 9 $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1486E/9c27ff1803f812784d9dc5ba8f09e905e17b3714.png)

Input

题意翻译

给定图 $G=\lang V,E\rang$(不一定保证 $G$ 是一个连通图),请你找到从 $1$ 开始到达任意一个点 $t(t\in [1,n])$ 的最短路长度。 但是每次你不能只走 $E$ 中的一条边,而是选择两条边 $e_1,e_2\in E\;\text{s.t.}\;e_1=\lang x,u,w_1\rang,e_2=\lang u,y,w_2\rang$,然后,执行 $x\overset{e_1}\rightarrow u\overset{e_2}\rightarrow y$ 且每次走的花费是 $(w_1+w_2)^2$. 保证 $|V|\le 10^5,|E|\le \min\left\{2\times 10^5,{|V|\times (|V|-1)\over 2}\right\},\forall e=\lang u,v,w\rang \in E,w\le 50$.

加入题单

算法标签: