次短路模板
2026-01-31 10:21:22
发布于：四川
1阅读
0回复
0点赞
//次短路模板
//洛谷P2865
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll; // 优先队列存储结构：(当前距离, 节点编号)，用于Dijkstra算法的优先级排序
const int inf = 0x3f3f3f3f; // 整数型无穷大，标记初始距离为不可达
const ll infl = 0x7fffffff;
const int maxn = 5e6 + 5; // 数组容量，适配邻接表最大边数（双向边需双倍空间）
// 链式前向星相关：高效存储图的边信息，适合稀疏图的邻接表表示
int head[maxn], node = 0; // head[u]：节点u的第一条边在edge数组中的索引 node：全局边计数器，初始化为0
struct Edge{
int v; // 边的终点节点编号，表示该边指向的相邻节点
int w; // 边的长度（权重），即通过该边所需的距离或成本
int pre; // 上一条边的索引，用于构建链式结构，实现快速遍历某个节点的所有邻接边
} edge[maxn * 2]; //无向图(两边都需存储)
// 向邻接表添加双向边（无向图）：同时添加u到v和v到u的边，确保两个方向都能被正确访问
inline void add_edge(int u, int v, int w){
edge[++node].v = v; // 设置当前边的终点为v，注意node从1开始计数，避免与head中的0冲突
edge[node].w = w; // 设置当前边的长度为w，记录该边的权重信息
edge[node].pre = head[u]; // 将当前边链接到u的前一条边上，形成以head[u]为头、当前边为尾的链式结构
head[u] = node; // 更新节点u的头指针，使其指向当前刚添加的边，完成u的邻接边的插入
}
ll dis[maxn]; // dis[u]：存储从起点s到节点u的最短路径长度，初始化为无穷大，后续逐步更新为实际最短距离
ll disc[maxn]; // disc[u]：存储从起点s到节点u的次短路径长度，要求严格大于最短路径，且尽可能小，同样初始化为无穷大
// 扩展Dijkstra算法：同步计算每个节点的最短路径和次短路径，适用于需要获取次优解的场景
void dj(int s){
// 初始化最短和次短路径为无穷大，表示初始状态下所有节点均未被访问，距离未知
memset(dis, inf, sizeof(dis));
memset(disc, inf, sizeof(disc));
// 小根堆：优先队列按距离从小到大排序，保证每次弹出的都是当前已知距离最小的节点(贪心策略)
priority_queue<pll, vector<pll>, greater<pll> > q;
dis[s] = 0; // 起点到自身的最短路径长度为0，因为不需要移动即可到达自身
q.push(make_pair(dis[s], s)); // 将起点加入优先队列，启动搜索过程，此时队列中只有起点一个元素
while (!q.empty()){
int u = q.top().second; // 取出队列中距离最小的节点u，作为当前要处理的节点
ll d = q.top().first; // 获取节点u的当前距离d，即当前已知的从起点到u的最短或次短路径长度
q.pop(); // 将节点u从队列中移除，准备处理其邻接节点
// 若当前距离d已经大于u的次短路径长度disc[u]，说明之前已经找到了更优的最短和次短路径，此次无需再处理u的邻接边，跳过以优化性能
if (d > disc[u]) continue;
// 遍历节点u的所有邻接边，尝试通过u扩展到其他节点，更新它们的最短或次短路径
for(int i = head[u]; i; i = edge[i].pre){
int v = edge[i].v; // 获取当前边的终点v，即u的相邻节点
ll new_d = d + edge[i].w; // 计算从起点经过u再到v的新路径长度new_d，等于u的当前距离加上u到v的边长
// 情况1：新路径长度new_d比v的最短路径dis[v]更短，说明找到了一条更优的最短路径
if(new_d < dis[v]){
// 原最短路径dis[v]降级为次短路径disc[v]，因为新的最短路径出现后，原来的最短路径成为次优选择
disc[v] = dis[v];
// 更新v的最短路径为新的更短路径new_d
dis[v] = new_d;
// 将新的最短路径对应的节点v及其距离入队，以便后续继续扩展v的邻接节点，传播最短路径信息
q.push(make_pair(dis[v], v));
}
// 情况2：新路径长度new_d介于v的最短路径dis[v]和次短路径disc[v]之间（即new_d > dis[v]且new_d < disc[v]），说明虽然不是最短，但可以作为更优的次短路径
if(new_d > dis[v] && new_d < disc[v]){
// 更新v的次短路径为新的路径长度new_d，替换掉原来较大的次短路径
disc[v] = new_d;
// 将新的次短路径对应的节点v及其距离入队，确保后续能基于此次短路径继续扩展到其他节点，完善次短路径的传播
q.push(make_pair(disc[v], v));
}
}
}
}
int main(){
int n, m, u, v, w;
cin >> n >> m; // 读取交叉路口数n（节点总数）和道路数m（边总数），构建城市交通网络模型
// 读取m条双向道路，构建邻接表表示的图结构，每条道路对应图中的两条有向边
for(int i = 1; i <= m; ++i){
cin >> u >> v >> w; // 读取一条道路的起点u、终点v和长度w
add_edge(u, v, w);//双向建边
add_edge(v, u, w);
}
dj(1); //计算所有节点到起点1的最短路径和次短路径
cout << disc[n] << endl; // 输出终点n的次短路径长度，即从起点1到终点n的第二短的路径距离，满足题目要求的次优解需求
return 0; // 程序正常结束，返回0，表示执行成功
}
这里空空如也
有帮助，赞一个