#P1462. P1462 通往奥格瑞玛的道路
P1462 通往奥格瑞玛的道路
P1462 通往奥格瑞玛的道路
普及+/提高 | 来源:洛谷 | 原题链接
题意
座城市、 条双向公路。经过城市 要交费 ;走一条公路损失 点血量;初始血量 。求一条 的路径,使得单次交费的最大值最小,且总损血 。无法到达输出 AFK。(注意 可为 ;两条边可能连接相同城市。)
输入格式
第一行 个正整数,。分别表示有 个城市, 条公路,歪嘴哦的血量为 。
接下来有 行,每行 个非负整数,。表示经过城市 ,需要交费 元。
再接下来有 行,每行 个正整数,()。表示城市 和城市 之间有一条公路,如果从城市 到城市 ,或者从城市 到城市 ,会损失 的血量。
输出格式
仅一个整数,表示歪嘴哦经过城市单次交费最大值的最小值。
如果他无法到达奥格瑞玛,输出 AFK。
输入输出样例
样例 1 输入
4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
样例 1 输出
10
数据范围
,,,,。
提示
考点:二分答案 + Dijkstra 判定。二分「单次最大交费」:只保留 的城市建图,Dijkstra 求最小总损血,判定 。易错点:① 答案集只需在已有 值里二分;② 也必须 (起点和终点也要交费);③ 全图都不可达(即 取最大仍到不了 )才输出 AFK;④ 「答案最小值」与 是两个不同的量,别混。