web analytics

[9-03]超载

超载(road.pas/c/cpp)

TL:1S ML:128MB
【Description】
J 省有 n 个城市,其中某些城市之间有双向道路相连。每条道路有一个载重量,只有重量
不超过这个载重量的车才能走这条道路。现在 J 省交通部门收到了一些形如(s,t,w)的通行
请求,表示一辆车想从 s 市到 t 市,车的重量是 w。你需要回复这辆车是否可能从 s 市
走到 t 市。
【Input】
第一行两个整数 n m q
接下来 m 行,每行三个整数 l r k,表示从 l 市与 r 市之间有一条载重量为 k 的路
接下来 q 行,每行三个整数 s t w,表示一个通行请求
【Output】
q 行,每行为一个回复。若回复为“可以”,输出”Yes”,否则输出”No”
【Sample Input】
3 2 2
1 2 1
2 3 2
1 3 1
1 3 2
【Sample Output】
Yes
No
//
重量为 2 的车不能从 1 走到 2【Hint】
30%的数据保证
n ≤ 1000; q ≤ 1000
100%的数据保证 1 ≤ n ≤ 10000; 1 ≤ m ≤ 30000; 1 ≤ q ≤ 10000;
100%的数据保证 s ≠ t; l ≠ r; 1 ≤ w, k ≤ 10000

分析:
首先跑最大生成树.
之后LCA寻找链接两点树上路径的最小值。
就好了。

Post a Comment

You must be logged in to post a comment.