← 返回题目列表

AtCoder · joi2008yo_f

F. 乘船游览

中文机器翻译题面 查看原题

配点: 100 点

問題

JOI国有,n 岛屿,每个岛屿都有 1 从 n 编号。现在,JOI国正在整备连接各岛屿之间的航线网络。

你在处理船票的售票中心工作。JOI国有很多人希望使用船只以尽可能便宜的方式在岛屿之间旅行,他们会在订单表上写上出发地和目的地,然后送到你这里。

你的工作是在收到客户的订单表后,立即通过换乘几艘船,计算出连接出发地和目的地航线的最便宜运费,并告知客户。

但是,根据行程,有时可能无法使用船舶旅行。这种情况下,需要告诉客户“无法使用船舶旅行”。此外,在JOI国,连接岛屿之间的新船舶陆续开始运营,你将随时收到这些信息。在回复客户时,必须重点参考最新信息。

当输入提供客户订单表或新开始运营的船舶航运信息时,请创建一个程序来生成对客户的回复。

另外,输入示例 1 和输出示例 1 的执行情况以图 1 显示。


入力

输入的 1 在线 2 整数 n, k (1 \leqq n \leqq 100,1 \leqq k \leqq 5\,000) 中有说明。这是指岛屿的数量为 n 在岛上,输入表示为 k + 1 行。

i + 1 行目 (1 \leqq i \leqq k) 中,3 个或 4 个整数以空格分隔书写。

  • 当第一个数字为 0 时,这一行表示顾客的订单票。
    这一行中 3 整数 0, a, b (1 \leqq a \leqq n,1 \leqq b \leqq n,a \neq b) 以空格分隔书写。
    这表示顾客提交了从岛 a 出发、以岛 b 为目的地的订单票。
  • 当第一个数字为 1 时,这一行表示新开始运营的船舶的运营信息。
    这一行中 4 整数 1, c, d, e (1 \leqq c \leqq n,1 \leqq d \leqq n,c \neq d,1 \leqq e \leqq 1\,000\,000) 已书写。
    这表示往返岛 c 和岛 d 的船舶新开始运营,该船舶从岛 c 到岛 d 的运输租赁,以及运往 d 到岛 c 的运输租赁,都 e 表示是这样的。
    从这一行起的订货单,对于这些订货单,也必须考虑这艘船舶并进行归还处理。

在最初的阶段,假设船舶一艘也没有运营。在输入中,表示船舶运营信息的行是 1\,000 行如下。另外,请注意,在岛与岛之间,有时会有多艘船舶航行。

出力

在输入中,表示订单票的行数 m 记作
输出是 由 m 行组成, 写入一个整数,表示对第i 行目 (1 \leqq i \leqq m) 中,i 订单的回复。
也就是说, 如果可以在第i 订单的出发地和目的地之间转乘多艘船旅行,请填写总票价的最小值。如果无法出行, 写入-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

另外,输入示例 1 和输出示例 1 船如何开始运营以及对客户订单的回复。 如下图所示 1 。


入力例 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