已同步至对应题目
这次GESP考的好水，还没有我上次六级难。
T2
题意（形式化）
给定一个无向图，包含 NNN 个节点和 MMM 条边。每条边有两个属性：权重 www 和美丽值 bbb。你需要找一条从节点 111 到节点 NNN 的路径，然后可以在这条路径上选择一条美丽值最大的边（如果有多条边美丽值相同且均为最大，则任选其一），将其权重改为 000。你的目标是使修改后的路径总权重（即路径上所有边的权重之和，但被选中的那条边计为 000）尽可能小。输出这个最小值。如果不存在从 111 到 NNN 的路径，输出 −1-1−1。
输入
第一行两个数，表示 NNN 和 MMM。
接下来 MMM 行，每行四个整数 u,v,w,bu,v,w,bu,v,w,b，表示从 www 到 vvv 连接一条无向边，权值为 www，美丽值为 bbb。
输出
输出一个数，从 111 到 nnn 表示路径权重之和最小值，若无法到达，输出 −1-1−1。
数据范围
对于所有数据：N≤5000,M≤5000,wi,bi≤109N \le 5000,M \le 5000,w_i,b_i\le 10^9N≤5000,M≤5000,wi ,bi ≤109。wi,biw_i,b_iwi ,bi 一定是非负整数
解题
思路
我们可以采用逆向思维：直接考虑修改哪条边为 000 并不容易，因为最短路本身依赖于哪条边被修改。不妨反过来，枚举哪条边作为路径上美丽值最大的边（即被修改为 000 的边），然后在此基础上求解最短路。具体地，对于每条边 iii（假设其美丽值为 bib_ibi ），我们强制它成为路径上美丽值最大的边（即所有经过的边的美丽值都不超过 bib_ibi ），并将该边的权重视为 000（因为它将被修改），然后求从 111 到 NNN的最短路。这样，对于每一个可能的美丽值上界 bib_ibi
，我们都能得到一个候选答案。最终取所有候选答案的最小值即可。注意，若某条边不在任何一条满足美丽值限制的路径上，则该枚举无效。如果不存在任何从 111 到 NNN 的路径，则输出 −1-1−1。
实现
使用链式前向星存边，枚举每条边（对与第 iii 条无向边边，在链式链式前向星里的下标是 i×2−1i \times 2 - 1i×2−1 和 i×2i \times 2i×2），将其 wiw_iwi 更改为 000，并在进行松弛操作时额外加上限制：该边的美丽值不能超过 bib_ibi 。后跑 MMM 次最短路求最小值即可。
考虑到每个人的链式前向星有自己的存储习惯，因此第 iii 条边的下标也会有所不同，顾贴出适合该题解的存储代码：
最后
遍历时只是假设第 iii 条边是美丽值最大的边，并不是强求要走第 iii 条边。
可以使用非链式前向星的方法，但是链式前向星是最容易实现的方法了。
理论复杂度是 O(m2logm)O(m^2\log m)O(m2logm)，实际运行时 bib_ibi 对于边的限制会大大减少时间复杂度，不会TLE。
