2997: 噪音恐惧症[Audio phobia,UVa10048]
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
噪音污染，已经成为城市污染的主要污染之一了。声音的强度通常以分贝来策略，超过130分贝的声音，就会让人感觉不舒服。
下图给出了一个城市地图，图中的点表示道路的交叉点，边表示道路，每条边上的整数表示相应道路上的声音强度，单位是分贝。
从交叉点A到交叉点G，不可以选择路线：A-C-F-G，这条路线中，比必须能够容忍高达140分贝的声音强度。同理路线A-B-E-G，路线A-B-D-G,路线A-C-F-D-G中比必须容忍的声音强度分别是90，120和80。
当然还有其他路线，但是，很明显A-C-F-D-G是最舒适路线，因为它的最大噪音值是80分贝。
给定一个城市地图，你需要回答出从一个点到另一点的所有路线中最大噪音的最小值。
下图给出了一个城市地图，图中的点表示道路的交叉点，边表示道路，每条边上的整数表示相应道路上的声音强度，单位是分贝。
从交叉点A到交叉点G，不可以选择路线：A-C-F-G，这条路线中，比必须能够容忍高达140分贝的声音强度。同理路线A-B-E-G，路线A-B-D-G,路线A-C-F-D-G中比必须容忍的声音强度分别是90，120和80。当然还有其他路线，但是，很明显A-C-F-D-G是最舒适路线，因为它的最大噪音值是80分贝。
给定一个城市地图，你需要回答出从一个点到另一点的所有路线中最大噪音的最小值。
Input
输入包含多组数据，对于每组数据。
第一行，三个整数，C,S,Q。C表示城市中的道路的交叉点数量，C≤100.S表示城市中道路的数量，S≤1000.Q表示问题的数量，Q≤10000.
接下来S行，每行三个整数，c1,c2,d,描述S到道路，表示从交叉点c1到c2这条道路上的声音强度是d。c1≠c2
接下来Q行，每行一个问题，包含两个整数c1和c2,询问从c1到c2的所有路线中最大噪音的最小值。c1≠c2
当输入为“0 0 0”时，表示输入结束
第一行，三个整数，C,S,Q。C表示城市中的道路的交叉点数量，C≤100.S表示城市中道路的数量，S≤1000.Q表示问题的数量，Q≤10000.
接下来S行，每行三个整数，c1,c2,d,描述S到道路，表示从交叉点c1到c2这条道路上的声音强度是d。c1≠c2
接下来Q行，每行一个问题，包含两个整数c1和c2,询问从c1到c2的所有路线中最大噪音的最小值。c1≠c2
当输入为“0 0 0”时，表示输入结束
Output
对于每组测试数据：
先输出一行“Case #X”，X表示测试数据的编号。
接下来Q行，每行一个整数，按照输入中问题的顺序，输出这次问题的结果。如果问题中的两个交叉点之间没有路径，输出“no path”
每组测试输出之间用一个空行隔开。
先输出一行“Case #X”，X表示测试数据的编号。
接下来Q行，每行一个整数，按照输入中问题的顺序，输出这次问题的结果。如果问题中的两个交叉点之间没有路径，输出“no path”
每组测试输出之间用一个空行隔开。
Sample Input Copy
7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
0 0 0
Sample Output Copy
Case #1
80
60
60
Case #2
40
no path
80