站外提求助

动态最短路 时间限制：1s 内存限制：256M 题目描述 给定一张 n 个点的有向带权图，初始时图中已经有 m 条边，你需要支持以下操作： add u v w：在图中增加一条从点 u 指向点 v 的边，边权为 w。 get u v：求当前图中从点 u 出发，到达点 v 的最短路径长度。 总共 q 次操作，对于所有的 get 操作，输出对应的最短路长度。 保证图中任何时候都不会有重边和自环。

【输入格式】

第一行，两个正整数 n,m。 接下来 m 行，每行三个正整数 u,v,w，分别表示一条边的起点，终点以及边权。

第 m+2 行，一个正整数 q。

接下来 q 行，每行一个操作，格式与题目描述相同。

【输出格式】

对于每次 get 操作，输出当时图中从点 u 出发，前往点 v 的最短路径长度，若不存在这样的路径，输出 −1。

【输入输出样例#1】 输入#1

4 4

1 3 5

1 2 2

2 3 1

4 1 3

4

get 4 3

get 1 4

add 2 4 4

get 1 4

输出#1

6

-1

6

【数据范围】 1 ≤ n ≤ 200 , 0 ≤ m ≤ n ( n − 1 ) 1≤n≤200,0≤m≤n(n−1)

对于每条边， 1 ≤ u , v ≤ n , u ≠ v , 1 ≤ w ≤ 1 0^ 6

add 和 get 操作的调用次数，各自不超过 100 100 次。