题意（形式化） 给定一个无向图，包含 NNN 个节点和 MMM 条边。每条边有两个属性：权重 www 和美丽值 bbb。你需要找一条从节点 111 到节点 NNN 的路径，然后可以在这条路径上选择一条美丽值最大的边（如果有多条边美丽值相同且均为最大，则任选其一），将其权重改为 000。你的目标是使修改后的路径总权重（即路径上所有边的权重之和，但被选中的那条边计为 000）尽可能小。输出这个最小值。如果不存在从 111 到 NNN 的路径，输出 −1-1−1。 解题 思路 我们可以采用逆向思维：直接考虑修改哪条边为 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(m2log⁡m)O(m^2\log m)O(m2logm)，实际运行时 bib_ibi 对于边的限制会大大减少时间复杂度，不会TLE。

大家好，我是ЭНТДЖЕЙ，今天是我2026年第十七次正式发题解！ 2026年发布的题解！ 能不能点个赞 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先简化题意： * 说白了题意没什么好简化的 然后就是写代码: * 这道题我认为是最好想但不那么好实现的题： * 其实就是用迪杰斯特拉来写，枚举所有免费边（可以没有）的情况，求最小值 最后输出（WRITE）： * 输出最小值 完整代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎉完结撒花🎉 这道题给绿高了

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; struct Edge{ int u,v; ll w,b; }e[5005]; vector<pair<int,ll>> g[5005]; int n,m; void spfa(vector<ll>& dis, const vector<int>& sources){ queue<int> q; vector<bool> inq(n+1,false); for(int x : sources){ if(!inq[x]){ q.push(x); inq[x]=true; } } while(!q.empty()){ int u = q.front(); q.pop(); inq[u]=false; for(auto &pr : g[u]){ int to = pr.first; ll w = pr.second; if(dis[to] > dis[u] + w){ dis[to] = dis[u] + w; if(!inq[to]){ inq[to]=true; q.push(to); } } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=0;i<m;i++){ cin>>e[i].u>>e[i].v>>e[i].w>>e[i].b; } sort(e,e+m,[](const Edge&a,const Edge&b){return a.b < b.b;}); }

第1次正经解题！！！ 难度：普及+/提高 比较难的七级题，比八级简单一点 正文： 关系到了一个“最短路径”的问题。自己去查 之后用BFS（广搜）就能摆平 看完去做一遍吧！You can do it!