#P1462. P1462 通往奥格瑞玛的道路

P1462 通往奥格瑞玛的道路

P1462 通往奥格瑞玛的道路

普及+/提高 | 来源:洛谷 | 原题链接

题意

nn 座城市、mm 条双向公路。经过城市 ii 要交费 fif_i;走一条公路损失 cic_i 点血量;初始血量 bb。求一条 1→n1\to n 的路径,使得单次交费的最大值最小,且总损血 ≤b\le b。无法到达输出 AFK。(注意 fif_i 可为 00;两条边可能连接相同城市。)

输入格式

第一行 33 个正整数,n,m,bn,m,b。分别表示有 nn 个城市,mm 条公路,歪嘴哦的血量为 bb。

接下来有 nn 行,每行 11 个非负整数,fif_i。表示经过城市 ii,需要交费 fif_i 元。

再接下来有 mm 行,每行 33 个正整数,ai,bi,cia_i,b_i,c_i(1≤ai,bi≤n1\leq a_i,b_i\leq n)。表示城市 aia_i 和城市 bib_i 之间有一条公路,如果从城市 aia_i 到城市 bib_i,或者从城市 bib_i 到城市 aia_i,会损失 cic_i 的血量。

输出格式

仅一个整数,表示歪嘴哦经过城市单次交费最大值的最小值。

如果他无法到达奥格瑞玛,输出 AFK。

输入输出样例

样例 1 输入

4 4 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

样例 1 输出

10

数据范围

1≤n≤1041\le n\le 10^4,1≤m≤5×1041\le m\le 5\times10^4,1≤b≤1091\le b\le 10^9,1≤ci≤1091\le c_i\le 10^9,0≤fi≤1090\le f_i\le 10^9。

提示

考点:二分答案 + Dijkstra 判定。二分「单次最大交费」xx:只保留 fi≤xf_i\le x 的城市建图,Dijkstra 求最小总损血,判定 ≤b\le b。易错点:① 答案集只需在已有 fif_i 值里二分;② f1,fnf_1,f_n 也必须 ≤x\le x(起点和终点也要交费);③ 全图都不可达(即 xx 取最大仍到不了 nn)才输出 AFK;④ 「答案最小值」与 bb 是两个不同的量,别混。

蜀ICP备2025119001号-1