7732: BZOJ3732:Network
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?
输入格式
第一行: N, M, K。
第2..M+1行: 三个正整数:X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?
输出格式
对每个询问,输出最长的边最小值是多少。
样例输入
6 6 8 1 2 5 2 3 4 3 4 3 1 4 8 2 5 7 4 6 2 1 2 1 3 1 4 2 3 2 4 5 1 6 2 6 1
样例输出
5 5 5 4 4 7 4 5
提示
1 <= N <= 15,000
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000
题目来源
没有写明来源