GESP 202603 T2题解
2026-03-15 11:12:49
发布于：广东
这次GESP考的好水，还没有我上次六级难。
T2
题意（形式化）
给定一个无向图，包含 个节点和 条边。每条边有两个属性：权重 和美丽值 。你需要找一条从节点 到节点 的路径，然后可以在这条路径上选择一条美丽值最大的边（如果有多条边美丽值相同且均为最大，则任选其一），将其权重改为 。你的目标是使修改后的路径总权重（即路径上所有边的权重之和，但被选中的那条边计为 ）尽可能小。输出这个最小值。如果不存在从 到 的路径，输出 。
输入
第一行两个数，表示 和 。
接下来 行，每行四个整数 ，表示从 到 连接一条无向边，权值为 ，美丽值为 。
输出
输出一个数，从 到 表示路径权重之和最小值，若无法到达，输出 。
数据范围
对于所有数据：。 一定是非负整数
解题
思路
我们可以采用逆向思维：直接考虑修改哪条边为 并不容易，因为最短路本身依赖于哪条边被修改。不妨反过来，枚举哪条边作为路径上美丽值最大的边（即被修改为 的边），然后在此基础上求解最短路。具体地，对于每条边 （假设其美丽值为 ），我们强制它成为路径上美丽值最大的边（即所有经过的边的美丽值都不超过 ），并将该边的权重视为 （因为它将被修改），然后求从 到 的最短路。这样，对于每一个可能的美丽值上界 ，我们都能得到一个候选答案。最终取所有候选答案的最小值即可。注意，若某条边不在任何一条满足美丽值限制的路径上，则该枚举无效。如果不存在任何从 到 的路径，则输出 。
实现
使用链式前向星存边，枚举每条边（对与第 条无向边边，在链式链式前向星里的下标是 和 ），将其 更改为 ，并在进行松弛操作时额外加上限制：该边的美丽值不能超过 。后跑 次最短路求最小值即可。
考虑到每个人的链式前向星有自己的存储习惯，因此第 条边的下标也会有所不同，顾贴出适合该题解的存储代码：
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;
}
最后
遍历时只是假设第 条边是美丽值最大的边，并不是强求要走第 条边。
可以使用非链式前向星的方法，但是链式前向星是最容易实现的方法了。
理论复杂度是 ，实际运行时 对于边的限制会大大减少时间复杂度，不会TLE。
全部评论 1
pair <int, pair <int, int>> dist[5005]; pair <int, int> e[5005][5005];
（未减路径，（最大风景度，最大风景度对应可以减小的路程））这个是dist
不减风景度的路程-（比风景度，相等取大，不相等取更大风景独对应的路程）
大概是这个样子，但是没找到hack昨天 来自 上海
0
有帮助，赞一个