题意（形式化）

给定一个无向图，包含 $N$ 个节点和 $M$ 条边。每条边有两个属性：权重 $w$ 和美丽值 $b$。你需要找一条从节点 $1$ 到节点 $N$ 的路径，然后可以在这条路径上选择一条美丽值最大的边（如果有多条边美丽值相同且均为最大，则任选其一），将其权重改为 $0$。你的目标是使修改后的路径总权重（即路径上所有边的权重之和，但被选中的那条边计为 $0$）尽可能小。输出这个最小值。如果不存在从 $1$ 到 $N$ 的路径，输出 $-1$。

解题

思路

我们可以采用逆向思维：直接考虑修改哪条边为 $0$ 并不容易，因为最短路本身依赖于哪条边被修改。不妨反过来，枚举哪条边作为路径上美丽值最大的边（即被修改为 $0$ 的边），然后在此基础上求解最短路。具体地，对于每条边 $i$（假设其美丽值为 $b_i$），我们强制它成为路径上美丽值最大的边（即所有经过的边的美丽值都不超过 $b_i$），并将该边的权重视为 $0$（因为它将被修改），然后求从 $1$ 到 $N$的最短路。这样，对于每一个可能的美丽值上界 $b_i$，我们都能得到一个候选答案。最终取所有候选答案的最小值即可。注意，若某条边不在任何一条满足美丽值限制的路径上，则该枚举无效。如果不存在任何从 $1$ 到 $N$ 的路径，则输出 $-1$。

实现

使用链式前向星存边，枚举每条边（对与第 $i$ 条无向边边，在链式链式前向星里的下标是 $i \times 2 - 1$ 和 $i \times 2$），将其 $w_i$ 更改为 $0$，并在进行松弛操作时额外加上限制：该边的美丽值不能超过 $b_i$。后跑 $M$ 次最短路求最小值即可。

考虑到每个人的链式前向星有自己的存储习惯，因此第 $i$ 条边的下标也会有所不同，顾贴出适合该题解的存储代码：

struct EDGE{
	int to , w , b , next;
}edge[M];
int head[M] , cnt = 0;
void Add(int u , int v , int w , int b){
	edge[++ cnt] = {v , w , b , head[u]};
	head[u] = cnt;
	edge[++ cnt] = {u , w , b , head[v]};
	head[v] = cnt;
}

最后

遍历时只是假设第 $i$ 条边是美丽值最大的边，并不是强求要走第 $i$ 条边。

可以使用非链式前向星的方法，但是链式前向星是最容易实现的方法了。

理论复杂度是 $O(m^2\log m)$，实际运行时 $b_i$ 对于边的限制会大大减少时间复杂度，不会TLE。