分层图模板
2026-01-31 10:21:58
发布于：四川
1阅读
0回复
0点赞
//分层图模板
//洛谷P4568
#include<bits/stdc++.h>
using namespace std; //使用标准命名空间，简化代码书写
typedef long long ll; //定义长整型，避免费用溢出（数据范围可能较大）
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll infl = 0x7fffffff;
const int maxn = 5e6 + 5; //数组容量，适配分层图总节点数（每层最多n个节点，共k+1层）
//链式前向星相关：高效存储分层图的边信息
int head[maxn], node = 0;//head[u]:节点u的第一条边索引 node:边计数器(初始化为0)
struct Edge{
int v; //边的终点节点编号
int w; //边的权重（花费），表示通过该边的费用
int pre; //上一条边的索引，用于链式遍历，构建邻接表
} edge[maxn * 2]; //存储所有边，双向边需双倍容量，确保足够存储所有连接关系
//向邻接表添加边（无向图需要添加两次，分别表示两个方向）
inline void add_edge(int u, int v, int w) {
edge[++node].v = v; //设置当前边的终点为v
edge[node].w = w; //设置当前边的权重为w
edge[node].pre = head[u]; //将当前边链接到u的前一条边上，形成链式结构
head[u] = node; //更新u的头指针指向当前边，完成边的添加
}
ll dis[maxn]; //存储从起点到各节点的最短花费，初始化为无穷大
bool vis[maxn]; //标记节点是否已确定最短花费，避免重复处理
//Dijkstra算法：计算从起点s到所有节点的最短路径，适用于非负权图
void dj(int s){
memset(dis, inf, sizeof(dis)); //初始化所有节点花费为无穷大，表示尚未到达
memset(vis, 0, sizeof(vis)); //初始化所有节点为未访问状态，准备开始搜索
//小根堆：优先弹出花费最小的节点，保证每次处理的都是当前最短路径的节点
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
q.pop();
if (vis[u]) continue; //如果u已经被处理过，跳过，避免重复计算
vis[u] = 1; //标记u的最短花费已确定，后续不再修改
//遍历u的所有邻接边，寻找更短的路径
for(int i = head[u]; i; i = edge[i].pre){
int v = edge[i].v;
//若v未被访问，且通过u→v的路径花费更低，则更新v的最短花费
if(!vis[v] && edge[i].w + dis[u] < dis[v]){
dis[v] = edge[i].w + dis[u];//更新v的最短花费为新找到的更小值
q.push(make_pair(dis[v], v));//将更新后的v重新加入队列，继续传播最短路径
}
}
}
}
int main(){
int n, m, k, s, t, u, v, w;
cin >> n >> m >> k >> s >> t;
s++;//节点编号加1，避免0号节点与分层索引冲突，便于数组操作
t++;
//构建分层图，模拟不同层次的使用情况
for(int i = 1; i <= m; ++i){
cin >> u >> v >> w;
u++;//原始节点编号加1，统一调整为基于1的索引
v++;
//第0层的双向边（正常付费），表示不使用特殊权限时的常规路径
add_edge(u, v, w);
add_edge(v, u, w);
//构建第1到k层的边，模拟使用不同次数的特殊权限后的情况
for(int j = 1; j <= k; ++j){
//层间边：从第j-1层到第j层，免费使用当前航线（权重0），表示使用了一次特殊权限
add_edge(u + (j - 1) * n, v + j * n, 0);
add_edge(v + (j - 1) * n, u + j * n, 0);
//第j层内的双向边（正常付费），表示使用完特殊权限后恢复常规付费模式
add_edge(u + j * n, v + j * n, w);
add_edge(v + j * n, u + j * n, w);
}
}
dj(s);//获取到所有节点的最短路径
//取终点t在所有层（0到k）的最小花费
ll ans = inf;
for(int i=0;i<=k;++i) {
ans = min(ans, dis[t + i*n]);//遍历所有层
}
cout<<ans<<endl;
return 0;
}
这里空空如也
有帮助，赞一个