loj#P3134. 「COCI 2019.2」Transport
「COCI 2019.2」Transport
题目描述
译自 COCI 2018/2019 Contest #5 T5「Transport」
某个遥远的国度一共有 个城市,这些城市由恰好 条路径连接,使得所有城市相互连通。每个城市都有且仅有一个加油站。已知每条路径的长度和每个加油站具有的燃料分量。
由于不久前刚经历过能源危机,行业协会想了解目前各个城市之间公路运输的能力。假设长途货车每行驶一公里距离要消耗一单位燃料,货车能够从城市 抵达某个相邻城市 当且仅当货车离开城市 时具有的燃料量大于或等于道路 的长度。每当货车抵达一个城市,可以在加油站补充不超过加油站燃料分量的燃料。
假设货车的油箱具有无限容量。请你计算,一共有多少个有序城市对 满足,油箱燃料最初为 的货车可以从城市 出发经过一些城市抵达城市 (货车离开城市 时会加满城市 的加油站燃料数)。
输入格式
第一行,是一个正整数 。
第二行,是 个正整数 ,依次表示城市 的加油站燃料量。
接下来 行,每行是三个正整数 ,表示存在一条连接城市 和城市 的长度为 公里的道路。
输出格式
一行一个整数,表示满足条件的点对数。
2
3 1
1 2 2
1
5
3 1 2 4 5
1 2 3
3 2 2
4 2 6
5 4 3
5
数据范围与提示
对于 的数据,$1\leq N\leq 10^5, 1\leq U, V\leq N, 1\leq A_i\leq 10^9, 1\leq W\leq 10^9$。