#P2683. 小岛
小岛
题目背景
西伯利亚北部的寒地,坐落着由 个小岛组成的岛屿群,我们把这些小岛依次编号为 到 。
题目描述
起初,岛屿之间没有任何的航线。后来随着交通的发展,逐渐出现了一些连通两座小岛的航线。例如增加一条在 号小岛与 号小岛之间的航线,这条航线的用时为 。那么沿着这条航线, 号小岛上的人可以前往 号小岛,同样的 号小岛上的人也可以前往 号小岛,其中沿着这一条航线花费的时间为 。
同时,随着旅游业的发展,越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。
输入格式
输入共 行。
第一行有两个整数 和 ,分别表示小岛的数与总操作数。
接下来的 行,每行表示一个操作,格式如下:
0 s t
:表示询问从 号小岛到 号小岛的最短用时()。
1 u v e
:表示新增了一条从 号小岛到 号小岛,用时为 的双向航线()。
输出格式
输出针对每一次询问,单独输出一行。
对于每一组询问来说,如果不存在可行的道路,则输出 -1
,否则输出最短用时。
3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3
-1
15
12
5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3
5955
21431
9298
16392
24774
8840
提示
对于 的数据, 且 。
对于 的数据, 且 。
对于 的数据, 且 。
对于 的数据, 且 。
对于 的数据, 且 。