F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 2125. -- 最短路

2125: 最短路

Time Limit: 1 Sec  Memory Limit: 259 MB
Submit: 2383  Solved: 972
[Submit][Status][Discuss]

Description

给一个N个点M条边的连通无向图,满足每条边最多属于一个环,有Q组询问,每次询问两点之间的最短路径。

Input

输入的第一行包含三个整数,分别表示N和M和Q 下接M行,每行三个整数v,u,w表示一条无向边v-u,长度为w 最后Q行,每行两个整数v,u表示一组询问

Output

输出Q行,每行一个整数表示询问的答案

Sample Input

9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7

Sample Output

5
6

HINT

对于100%的数据,N<=10000,Q<=10000

Source

[Submit][Status][Discuss]

HOME Back