P2683 小岛

    • 204通过
    • 547提交
  • 题目提供者 x_faraway_x
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    西伯利亚北部的寒地,坐落着由 N 个小岛组成的岛屿群,我们把这些小岛依次编号为 1 到 N 。

    题目描述

    起初,岛屿之间没有任何的航线。后来随着交通的发展,逐渐出现了一些连通两座小岛的航线。例如增加一条在 u 号小岛与 v 号小岛之间的航线,这条航线的用时为 e。 那么沿着这条航线,u 号小岛上的人可以前往 v 号小岛,同样的 v 号小岛上的人也可以前往 u 号小岛,其中沿着这一条航线花费的时间为 e。

    同时,随着旅游业的发展,越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。

    输入输出格式

    输入格式:

    输入共 M+1 行。

    第一行有两个整数 N 和 M,分别表示小岛的数与总操作数。

    接下来的 M 行,每行表示一个操作,格式如下:

    0 s t:表示询问从 s 号小岛到 t 号小岛的最短用时(1<=s<=n, 1<=t<=n, s\neq t)。

    1 u v e:表示新增了一条从 u 号小岛到 v 号小岛,用时为 e 的双向航线(1<=u<=n, 1<=v<=n, u ≠ v, 1<=e<=10^6)。

    输出格式:

    输出针对每一次询问,单独输出一行。

    对于每一组询问来说,如果不存在可行的道路,则输出 -1,否则输出最短用时。

    输入输出样例

    输入样例#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: 复制
    -1
    15
    12
    输入样例#2: 复制
    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
    输出样例#2: 复制
    5955
    21431
    9298
    16392
    24774
    8840

    说明

    对于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。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。