1920: bellmanford板子
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：5
Solved：5
Description
给你一张 n 个顶点 m 条边的有向简单图，顶点编号从 1 到 n，每条边都有一个边权，边权为非负整数。
现在有 k 组询问，每组询问读入两个整数 x,y 请求出从 x 号点到 y 号点的最短路的长度。如果不存在从 x 号点到 y 号点的路径，请输出 -1
现在有 k 组询问，每组询问读入两个整数 x,y 请求出从 x 号点到 y 号点的最短路的长度。如果不存在从 x 号点到 y 号点的路径，请输出 -1
Input
第一行三个整数 n,m,k表示图的顶点数、边数和询问次数。
接下来 m𝑚 行，每行三个整数 x,y,z表示 x𝑥 号点到 y 号点有一条边权为 z 的有向边。
接下来 k 行，每行两个整数 x,y表示一组询问。
接下来 m𝑚 行，每行三个整数 x,y,z表示 x𝑥 号点到 y 号点有一条边权为 z 的有向边。
接下来 k 行，每行两个整数 x,y表示一组询问。
Output
输出共 k 行，每行一个数表示一组询问的答案。
Sample Input Copy
3 3 2
1 2 3
2 3 2
3 2 1
1 3
3 1Sample Output Copy
5
-1