这个代码实现了一种结合 连通块分解、拓扑排序 和 Dijkstra 算法 的复杂图的最短路径计算方法,适用于含有两类边的图结构:普通边(在连通块内)和特殊边(跨连通块)。
以下是详细的代码讲解,逐步解析每一部分:
代码结构
1. 数据结构定义
const int N = 25010, M = 150010;
int n, mr, mp, S; // 城镇数量、普通边数量、特殊边数量、起点
int h[N], e[M], ne[M], w[M], idx; // 邻接表存储图
int id[N]; // 每个点属于的连通块编号
vector<int> block[N]; // 每个连通块包含的点
int bid; // 连通块编号
int dist[N]; // 到起点的最短距离
int din[N]; // 每个连通块的入度
bool st[N]; // 标记点是否已经确定最短距离
queue<int> q; // 队列用于拓扑排序
解释
- 邻接表:使用链式前向星存储普通边和特殊边。
h[u]
:存储节点u
的第一条边索引。e[idx], w[idx], ne[idx]
:分别表示边的目标节点、权重和下一条边的索引。
- 连通块:
id[u]
:标记节点 (u) 属于哪个连通块。block[bid]
:存储每个连通块的节点集合。
- 其他变量:
dist[u]
:起点到节点 (u) 的最短路径长度。din[id]
:每个连通块的入度。st[u]
:标记节点是否已确定最短距离。
2. 边的添加
void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
- 使用链式前向星添加边:
e[idx]
:目标节点。w[idx]
:边权重。ne[idx]
:指向当前节点的下一条边。
3. 连通块分解
void dfs(int u, int bid) {id[u] = bid; // 标记节点 u 属于连通块 bidblock[bid].push_back(u); // 将节点 u 加入连通块for (int i = h[u]; ~i; i = ne[i]) { // 遍历所有普通边int j = e[i];if (!id[j]) dfs(j, bid); // 如果未访问,则递归}
}
- 核心思想:通过深度优先搜索 (DFS),将图分解成连通块。
- 连通块标记:每个连通块分配一个唯一编号
bid
,节点u
的连通块编号存储在id[u]
中。 - 只处理普通边:连通块内部的边仅由普通边组成。
4. 连通块内部的 Dijkstra
void dijkstra(int bid) {priority_queue<PII, vector<PII>, greater<PII>> heap;// 将连通块中的所有点加入优先队列for (auto ver : block[bid]) heap.push({dist[ver], ver});while (heap.size()) {auto t = heap.top();heap.pop();int ver = t.y, distance = t.x;if (st[ver]) continue; // 如果最短路径已确定,跳过st[ver] = true;for (int i = h[ver]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > dist[ver] + w[i]) {dist[j] = dist[ver] + w[i];if (id[j] == id[ver]) heap.push({dist[j], j}); // 同连通块内继续松弛}// 如果跨连通块,更新入度并加入拓扑排序队列if (id[j] != id[ver] && --din[id[j]] == 0) q.push(id[j]);}}
}
- 功能:在连通块内部运行 Dijkstra 算法。
- 松弛规则:
- 如果邻接点属于同一个连通块,则更新距离并入队。
- 如果跨连通块,则更新目标连通块的入度,入度为 0 时加入拓扑队列。
5. 拓扑排序 + Dijkstra
void topsort() {memset(dist, 0x3f, sizeof dist); // 初始化最短距离为无穷大dist[S] = 0; // 起点距离为 0for (int i = 1; i <= bid; i++) // 入度为 0 的连通块入队if (din[i] == 0) q.push(i);while (q.size()) {auto t = q.front();q.pop();dijkstra(t); // 对当前连通块运行 Dijkstra}
}
- 功能:通过拓扑排序计算跨连通块的最短路径。
- 实现:
- 初始化所有入度为 0 的连通块,将其加入队列。
- 按照拓扑顺序依次处理连通块。
- 对于每个连通块,调用
dijkstra
计算其内部的最短路径,并更新跨连通块的依赖关系。
6. 主函数
int main() {cin >> n >> mr >> mp >> S;memset(h, -1, sizeof h); // 初始化邻接表// 读取普通边并构建邻接表while (mr--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}// 连通块分解for (int i = 1; i <= n; i++)if (!id[i]) dfs(i, ++bid);// 读取特殊边并更新入度while (mp--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);din[id[b]]++;}topsort(); // 拓扑排序 + 最短路径// 输出结果for (int i = 1; i <= n; i++)if (dist[i] > 0x3f3f3f3f / 2) puts("NO PATH");else cout << dist[i] << endl;return 0;
}
代码流程总结
-
普通边与特殊边的构建:
- 普通边用于连通块分解。
- 特殊边用于跨连通块的连接,记录连通块之间的依赖关系。
-
连通块分解:
- 使用 DFS 将图分解为多个连通块,每个连通块内部通过普通边连接。
-
拓扑排序:
- 根据特殊边建立连通块之间的依赖关系,通过拓扑排序处理连通块。
-
Dijkstra + 松弛更新:
- 在连通块内部运行 Dijkstra 算法,计算最短路径。
- 跨连通块时,使用拓扑顺序更新依赖连通块的最短路径。
-
输出结果:
- 若某节点不可达,输出
NO PATH
。 - 否则,输出从起点到每个节点的最短距离。
- 若某节点不可达,输出
时间复杂度
- 连通块分解:(O(n + mr))(DFS 遍历所有节点和普通边)。
- 拓扑排序:(O(b + mp))(连通块数 (b) 和特殊边数 (mp))。
- Dijkstra:(O(\text{总点数} \cdot \log(\text{总点数})))。
整体复杂度:(O(n + m + b \cdot \log n)),适合稀疏图和多连通块场景。
这段代码巧妙结合了 连通块分解 和 拓扑排序 的思想,高效处理了含两类边的复杂最短路径问题。