0
已解决
新手天翼
题目描述 Description
在遥远的山区里有n个村庄，这些村庄一次编号为1~n。有些村庄之间是有道路相通（互通）的，有些村庄之间还没有道路相通，但是以后会修建道路。现在请你编写一个程序，帮助管理记录这些村庄之间的路线。 程序需要支持两个功能： 添加新的路线信息 查询从村庄a到b的最短路径 添加路线信息的格式为： 1 a b s 意思是添加路线信息a与b互通，道路距离为s 查询路线信息的格式为： 0 a b 意思是查询a、b村庄的最短路径，若a、b之间尚无道路则输出-1，否则输出a、b的最短路径
输入描述 Input Description
第一行输入两个整数n，m，空格隔开。n表示村庄数量，m表示操作数量
接下来的m行，输入m个操作（添加路线、查询）
输出描述 Output Description
按顺序分行输出每次查询的结果。
样例输入 Sample Input
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
样例输出 Sample Output
-1
15
12
数据范围及提示 Data Size & Hint
对于20%的数据，N<=5且M<=30。
对于40%的数据，N<=20且M<=200。
对于60%的数据，N<=80且M<=500。
对于80%的数据，N<=100且M<=2500。
对于100%的数据，N<=100且M<=5000。
距离1<=s<=100000
0
已采纳
新手天翼
不会
0
中级天翼
1
0
资深守护
要不是题号我不会进来
0
新手守护
这个题号好坑呀
0
初级天翼
我同张梓沫的话。
0
新手天翼
不是题号，题号我都没注意，主要看题！
0
高级光能
最短路径。。。。。
em…………
谁学过图论，快来！
0
新手守护
阿凡达发电恢复第三个是否跟你说过
