题解：关于带约束条件的图的最短路径问题

一、题目背景

给定一个包含 (n) 个节点的图，图中存在两种类型的边，分别用于构建一些连通块（由 (mr) 条边构建）以及连接不同连通块（由 (mp) 条边构建）。此外，给定一个起点 (S)，要求计算从起点 (S) 到图中每个节点的最短路径。若无法到达某个节点，则输出 NO PATH。

二、代码整体思路

代码主要通过以下几个步骤来求解最短路径问题：
1. 读取图的相关信息，包括节点数 (n)、用于构建连通块的边数 (mr)、用于连接连通块的边数 (mp) 以及起点 (S)，并构建图的邻接表。
2. 通过深度优先搜索（DFS）将图划分成若干个连通块，为每个连通块分配一个唯一的编号，并记录每个节点所属的连通块编号。
3. 对每个连通块内的边权进行初始化，并通过拓扑排序结合 Dijkstra 算法来计算从起点 (S) 到各个节点的最短路径。
4. 输出从起点 (S) 到每个节点的最短路径，若无法到达则输出 NO PATH。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int n, mr, mp, S;
int id[N];
int h[N], e[M], w[M], ne[M], idx;
int dist[N], din[N];
vector<int> block[N];
int bcnt;
bool st[N];
queue<int> q;

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供 C++ 风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数，如 min、max 等。
   • #include <vector>：引入向量容器，用于存储连通块内的节点。
   • #include <queue>：引入队列和优先队列容器，用于拓扑排序和 Dijkstra 算法。
   • #define x first 和 #define y second：为 pair 类型的 first 和 second 成员定义别名，方便使用。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 25010：定义节点的最大数量。
   • const int M = 150010：定义边的最大数量。
   • const int INF = 0x3f3f3f3f：定义一个极大值，用于表示初始时的无穷距离。
3. 变量定义：
   • int n, mr, mp, S;：n 表示图的节点数，mr 表示用于构建连通块的边的数量，mp 表示用于连接连通块的边的数量，S 表示起点。
   • int id[N];：用于记录每个节点所属的连通块编号。
   • int h[N], e[M], w[M], ne[M], idx;：用于构建邻接表存储图的结构。h[i] 表示节点 i 的第一条边在 e 和 ne 数组中的下标；e[j] 表示第 j 条边的另一端点；w[j] 表示第 j 条边的权值；ne[j] 表示与第 j 条边同起点的下一条边的下标；idx 是边的计数器，用于记录当前已添加边的数量。
   • int dist[N], din[N];：dist[i] 用于记录从起点到节点 i 的最短距离，din[i] 用于记录连通块 i 的入度（即连接到该连通块的边的数量）。
   • vector<int> block[N];：block[i] 用于存储编号为 i 的连通块内的所有节点。
   • int bcnt;：记录连通块的数量。
   • bool st[N];：标记数组，用于标记每个节点是否已经被访问过。
   • queue<int> q;：队列，用于拓扑排序过程中存储入度为 (0) 的连通块编号。

（二）add 函数

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

该函数用于向邻接表中添加一条从节点 a 到节点 b，权值为 c 的边。具体操作是将节点 b 存储到 e[idx]，边权 c 存储到 w[idx]，将原来节点 a 的第一条边的下标存储到 ne[idx]，然后更新 h[a] 为当前边的下标 idx，最后 idx 自增 1，以便添加下一条边。

（三）dfs 函数

void dfs(int u, int bid)
{
    id[u] = bid, block[bid].push_back(u);

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!id[j])
            dfs(j, bid);
    }
}

1. 函数接受当前节点 u 和连通块编号 bid 作为参数。
2. 将节点 u 的连通块编号设置为 bid，并将节点 u 添加到编号为 bid 的连通块的节点列表中（block[bid].push_back(u);）。
3. 遍历节点 u 的所有邻接边（通过 for (int i = h[u]; ~i; i = ne[i]) 遍历邻接表）：
   • 获取邻接节点 j（j = e[i]）。
   • 如果邻接节点 j 还没有被分配连通块编号（!id[j]），则递归调用 dfs(j, bid)，将节点 j 也划分到当前连通块中。

（四）dijkstra 函数

void dijkstra(int bid)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for (auto u : block[bid])
        heap.push({dist[u], u});

    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 (id[j] != id[ver] && -- din[id[j]] == 0) q.push(id[j]);
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                if (id[j] == id[ver]) heap.push({dist[j], j});
            }
        }
    }
}

1. 初始化优先队列：
   • priority_queue<PII, vector<PII>, greater<PII>> heap;：创建一个小根堆优先队列 heap，用于存储节点及其到起点的距离。
   • for (auto u : block[bid]) heap.push({dist[u], u});：将当前连通块 bid 内的所有节点及其当前距离（dist[u]）加入优先队列。
2. Dijkstra 算法过程：
   • while (heap.size())：当优先队列不为空时，进行循环。
   • auto t = heap.top(); heap.pop();：取出队头元素 t，并将其从优先队列中删除。
   • int ver = t.y, distance = t.x;：获取节点编号 ver 和距离 distance。
   • if (st[ver]) continue;：如果节点 ver 已经被访问过，则跳过本次循环。
   • st[ver] = true;：标记节点 ver 为已访问。
   • 对于节点 ver 的每一条邻接边（通过 for (int i = h[ver]; ~i; i = ne[i]) 遍历邻接表）：
     • 获取邻接节点 j（j = e[i]）。
     • 如果邻接节点 j 所属的连通块与当前连通块不同（id[j] != id[ver]），并且邻接节点 j 所属连通块的入度减 (1) 后变为 (0)（-- din[id[j]] == 0），则将该连通块编号加入队列 q（q.push(id[j]);）。
     • 如果从起点到邻接节点 j 的距离大于从起点到节点 ver 的距离加上边 (ver, j) 的权值（dist[j] > dist[ver] + w[i]），则更新 dist[j] 为 dist[ver] + w[i]。
     • 如果邻接节点 j 与节点 ver 属于同一个连通块（id[j] == id[ver]），则将节点 j 及其新的距离加入优先队列（heap.push({dist[j], j});）。

（五）topsort 函数

void topsort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    for (int i = 1; i <= bcnt; i ++ )
        if (!din[i])
            q.push(i);

    while (q.size())
    {
        int t = q.front();
        q.pop();
        dijkstra(t);
    }
}

1. 初始化距离数组：
   • memset(dist, 0x3f, sizeof dist);：将 dist 数组初始化为一个较大的值（0x3f 表示十六进制的较大数，这里用于表示初始时的无穷距离）。
   • dist[S] = 0;：设置起点 S 到自身的距离为 (0)。
2. 拓扑排序初始化：
   • for (int i = 1; i <= bcnt; i ++ ) if (!din[i]) q.push(i);：遍历所有连通块，将入度为 (0) 的连通块编号加入队列 q。
3. 拓扑排序过程：
   • while (q.size())：当队列不为空时，进行循环。
   • int t = q.front(); q.pop();：取出队头元素 t，并将其从队列中删除。
   • dijkstra(t);：对编号为 t 的连通块调用 dijkstra 函数，计算该连通块内节点的最短距离。

（六）main 函数

int main()
{
    cin >> n >> mr >> mp >> S;
    memset(h, -1, sizeof h);

    while (mr -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    for (int i = 1; i <= n; i ++ )
        if (!id[i])
        {
            bcnt ++ ;
            dfs(i, bcnt);
        }

    while (mp -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        din[id[b]] ++ ;
        add(a, b, c);
    }

    topsort();

    for (int i = 1; i <= n; i ++ )
        if (dist[i] > INF / 2) cout << "NO PATH" << endl;
        else cout << dist[i] << endl;

    return 0;
}

1. 输入图的信息：
   • cin >> n >> mr >> mp >> S;：读取图的节点数 n、用于构建连通块的边数 mr、用于连接连通块的边数 mp 以及起点 S。
   • memset(h, -1, sizeof h);：将邻接表头数组 h 初始化为 (-1)，表示每个节点的第一条边还未添加。
   • 通过循环 while (mr -- ) 读取用于构建连通块的每一条边的两个端点 a 和 b 以及边权 c，并通过 add(a, b, c), add(b, a, c); 在邻接表中添加双向边。
2. 划分连通块：
   • 通过循环 for (int i = 1; i <= n; i ++ ) 遍历所有节点：
     • 如果节点 i 还没有被分配连通块编号（!id[i]），则连通块数量 bcnt 加 (1)，并调用 dfs(i, bcnt) 将节点 i 及其所属的连通块内的其他节点划分到新的连通块中。
3. 处理连接连通块的边：
   • 通过循环 while (mp -- ) 读取用于连接连通块的每一条边的两个端点 a 和 b 以及边权 c：
     • 将目标节点 b 所属连通块的入度加 (1)（din[id[b]] ++ ;）。
     • 通过 add(a, b, c); 在邻接表中添加边。
4. 计算最短路径：
   • topsort();：调用 topsort 函数，通过拓扑排序结合 Dijkstra 算法计算从起点 S 到各个节点的最短路径。
5. 输出结果：
   • 通过循环 for (int i = 1; i <= n; i ++ ) 遍历所有节点：
     • 如果从起点到节点 i 的距离大于极大值的一半（dist[i] > INF / 2），说明无法到达该节点，输出 NO PATH。
     • 否则输出从起点到节点 i 的最短距离（cout << dist[i] << endl;）。
6. 结束程序：
   • return 0;：程序正常结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 构建邻接表：添加 mr + mp 条边，每次添加边的操作时间复杂度为 (O(1))，所以构建邻接表的时间复杂度为 (O(mr + mp))。
2. 划分连通块（DFS）：每个节点最多被访问一次，时间复杂度为 (O(n))。
3. 拓扑排序和 Dijkstra 算法：
   • 拓扑排序过程中，每个连通块最多入队和出队一次，时间复杂度为 (O(bcnt))。
   • Dijkstra 算法在每个连通块内，每个节点最多入队和出队一次，每条边最多被访问一次，对于每个连通块的时间复杂度为 (O(|V| + |E|))（其中 (|V|) 是连通块内的节点数，(|E|) 是连通块内的边数），所有连通块的总时间复杂度为 (O(\sum_{i = 1}^{bcnt} (|V_i| + |E_i|)) = O(n + m))（因为 (\sum_{i = 1}^{bcnt} |V_i| = n)，(\sum_{i = 1}^{bcnt} |E_i| = m)）。
4. 总体时间复杂度为 (O(mr + mp + n + n + m) = O(mr + mp + n + m))，由于 (mr + mp) 与 (m) 相关，实际时间复杂度主要取决于 (n) 和 (m) 的数量级，时间复杂度近似为 (O(n + m))。

（二）空间复杂度

1. 邻接表存储图结构：边的数量最多为 M = 150010，节点的数量为 N = 25010，所以邻接表的空间复杂度为 (O(N + M) = O(N + 2N) = O(N))（这里边数 (M) 与节点数 (N) 有一定关系，实际空间复杂度主要由 (N) 和 (M) 决定）。
2. 存储连通块信息：id[N]