这个代码实现了一种结合 连通块分解、拓扑排序 和 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; // 队列用于拓扑排序

解释

1. 邻接表：使用链式前向星存储普通边和特殊边。
   • h[u]：存储节点 u 的第一条边索引。
   • e[idx], w[idx], ne[idx]：分别表示边的目标节点、权重和下一条边的索引。
2. 连通块：
   • id[u]：标记节点 (u) 属于哪个连通块。
   • block[bid]：存储每个连通块的节点集合。
3. 其他变量：
   • 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}
}

• 功能：通过拓扑排序计算跨连通块的最短路径。
• 实现：
  1. 初始化所有入度为 0 的连通块，将其加入队列。
  2. 按照拓扑顺序依次处理连通块。
  3. 对于每个连通块，调用 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;
}

---

代码流程总结

1. 普通边与特殊边的构建：

   • 普通边用于连通块分解。
   • 特殊边用于跨连通块的连接，记录连通块之间的依赖关系。

2. 连通块分解：

   • 使用 DFS 将图分解为多个连通块，每个连通块内部通过普通边连接。

3. 拓扑排序：

   • 根据特殊边建立连通块之间的依赖关系，通过拓扑排序处理连通块。

4. Dijkstra + 松弛更新：

   • 在连通块内部运行 Dijkstra 算法，计算最短路径。
   • 跨连通块时，使用拓扑顺序更新依赖连通块的最短路径。

5. 输出结果：

   • 若某节点不可达，输出 NO PATH。
   • 否则，输出从起点到每个节点的最短距离。

---

时间复杂度

1. 连通块分解：(O(n + mr))（DFS 遍历所有节点和普通边）。
2. 拓扑排序：(O(b + mp))（连通块数 (b) 和特殊边数 (mp)）。
3. Dijkstra：(O(\text{总点数} \cdot \log(\text{总点数})))。

整体复杂度：(O(n + m + b \cdot \log n))，适合稀疏图和多连通块场景。

---

这段代码巧妙结合了 连通块分解 和 拓扑排序 的思想，高效处理了含两类边的复杂最短路径问题。