题解：关于带权无向图中路径花费限制问题

一、题目背景

给定一个有 (n) 个点和 (m) 条边的带权无向图，每条边有一个权值。从点 (1) 走到点 (n)，可以将图中的某些边的权值视为 (1)（当边权大于某个阈值时），其余边权视为 (0)（当边权小于等于该阈值时），要求找到一个最小的阈值，使得从点 (1) 到点 (n) 经过权值为 (1) 的边的数量不超过 (k)。如果不存在这样的阈值，则输出 (-1)。

二、代码整体思路

代码主要通过二分查找阈值的方式，结合双端队列优化的广度优先搜索（BFS）来求解最小阈值。具体步骤如下：
1. 读取图的节点数 (n)、边数 (m) 和限制值 (k)，并构建图的邻接表。
2. 对可能的阈值范围进行二分查找。
3. 对于每个二分得到的阈值，调用 check 函数进行验证，该函数使用双端队列优化的 BFS 来计算从点 (1) 到点 (n) 经过权值为 (1) 的边的数量是否不超过 (k)。
4. 根据二分查找的结果输出最终答案，如果找不到满足条件的阈值则输出 (-1)。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

const int N = 1010, M = 20010;

int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
deque<int> q;
bool st[N];

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供 C++ 风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数，如 min、max 和二分查找相关的函数。
   • #include <deque>：引入双端队列容器，用于实现双端队列优化的 BFS。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 1010：定义节点的最大数量。
   • const int M = 20010：定义边的最大数量。
3. 变量定义：
   • int n, m, k;：n 表示图的节点数，m 表示边的数量，k 表示从点 (1) 到点 (n) 经过权值为 (1) 的边的最大允许数量。
   • 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];：用于记录从点 (1) 到每个点经过权值为 (1) 的边的最少数量。
   • deque<int> q;：双端队列，用于 BFS 过程中存储待处理的节点。
   • bool st[N];：标记数组，用于标记每个节点是否已经被访问过。

（二）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，以便添加下一条边。

（三）check 函数

bool check(int bound)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    q.push_back(1);
    dist[1] = 0;

    while (q.size())
    {
        int t = q.front();
        q.pop_front();

        if (st[t]) continue;
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], x = w[i] > bound;
            if (dist[j] > dist[t] + x)
            {
                dist[j] = dist[t] + x;
                if (!x) q.push_front(j);
                else q.push_back(j);
            }
        }
    }

    return dist[n] <= k;
}

1. 初始化：
   • memset(dist, 0x3f, sizeof dist);：将 dist 数组初始化为一个较大的值（0x3f 表示十六进制的较大数，这里用于表示未访问过的节点到点 (1) 的距离），用于记录从点 (1) 到每个点经过权值为 (1) 的边的最少数量。
   • memset(st, 0, sizeof st);：将 st 数组初始化为 false，表示所有节点都未被访问过。
   • q.push_back(1);：将起点 (1) 加入双端队列 q。
   • dist[1] = 0;：设置点 (1) 到自身经过权值为 (1) 的边的数量为 (0)。
2. BFS 过程：
   • while (q.size())：当双端队列不为空时，进行循环。
   • int t = q.front(); q.pop_front();：取出队头节点 t，并将其从队列中删除。
   • if (st[t]) continue;：如果节点 t 已经被访问过，则跳过本次循环。
   • st[t] = true;：标记节点 t 为已访问。
   • 对于节点 t 的每一条邻接边（通过 for (int i = h[t]; ~i; i = ne[i]) 遍历邻接表）：
     • int j = e[i], x = w[i] > bound;：获取邻接节点 j，并判断边 (t, j) 的权值是否大于阈值 bound，如果大于则 x 为 1，否则为 0。
     • if (dist[j] > dist[t] + x)：如果从点 (1) 到节点 j 经过权值为 (1) 的边的数量大于从点 (1) 到节点 t 经过权值为 (1) 的边的数量加上 x，则更新 dist[j] 为 dist[t] + x。
     • 根据边权与阈值的关系决定将节点 j 加入双端队列的前端还是后端：如果 x 为 0（边权小于等于阈值），则 q.push_front(j);，将节点 j 加入队列前端；如果 x 为 1（边权大于阈值），则 q.push_back(j);，将节点 j 加入队列后端。
3. 返回结果：
   • return dist[n] <= k;：如果从点 (1) 到点 (n) 经过权值为 (1) 的边的数量不超过 (k)，则返回 true，否则返回 false。

（四）main 函数

int main()
{
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e6 + 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    if (r == 1e6 + 1) cout << -1 << endl;
    else cout << r << endl;

    return 0;
}

1. 输入图的信息：
   • cin >> n >> m >> k;：读取图的节点数 n、边数 m 和限制值 k。
   • memset(h, -1, sizeof h);：将邻接表头数组 h 初始化为 (-1)，表示每个节点的第一条边还未添加。
   • 通过循环 while (m -- ) 读取每一条边的两个端点 a 和 b 以及边权 c，并通过 add(a, b, c), add(b, a, c); 在邻接表中添加双向边。
2. 二分查找阈值：
   • int l = 0, r = 1e6 + 1;：初始化二分查找的左边界 l 为 (0)，右边界 r 为一个较大的值（1e6 + 1）。
   • while (l < r)：当左边界小于右边界时，进行循环。
   • int mid = l + r >> 1;：计算中间值 mid，这里使用位运算 >> 1 相当于除以 (2)。
   • if (check(mid)) r = mid; else l = mid + 1;：调用 check 函数验证中间值 mid 是否满足条件（从点 (1) 到点 (n) 经过权值为 (1) 的边的数量不超过 (k)），如果满足则更新右边界 r 为 mid，否则更新左边界 l 为 mid + 1。
3. 输出结果：
   • if (r == 1e6 + 1) cout << -1 << endl; else cout << r << endl;：如果最终右边界 r 等于初始的较大值 1e6 + 1，说明没有找到满足条件的阈值，输出 (-1)；否则输出最终找到的最小阈值 r。
4. 结束程序：
   • return 0;：程序正常结束。

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

（一）时间复杂度

1. 构建邻接表：添加 m 条边，每次添加边的操作时间复杂度为 (O(1))，所以构建邻接表的时间复杂度为 (O(m))。
2. 二分查找：二分查找的次数最多为 (\log_{2}(1e6 + 1)) 次，每次二分查找调用 check 函数。
3. check 函数：check 函数中，每个节点最多入队和出队一次，每条边最多被访问一次，时间复杂度为 (O(n + m))。
4. 总体时间复杂度为 (O(m + \log_{2}(1e6 + 1) \times (n + m)) = O(m + \log(1e6 + 1) \times (n + m)))，由于 (n) 和 (m) 的关系以及常数项等因素，在实际中主要取决于 (m) 和 (n + m) 的数量级，时间复杂度近似为 (O(m + \log(1e6 + 1) \times (n + m)))。

（二）空间复杂度

1. 邻接表存储图结构：边的数量最多为 M = 20010，节点的数量为 N = 1010，所以邻接表的空间复杂度为 (O(N + M) = O(N + 2N) = O(N))（这里边数 (M) 与节点数 (N) 有一定关系，实际空间复杂度主要由 (N) 和 (M) 决定）。
2. dist 数组和 st 数组：dist[N] 数组和 st[N] 数组都占用 (O(N)) 的空间。
3. 双端队列 q：在最坏情况下，双端队列中可能存储所有节点，所以空间复杂度为 (O(N))。
4. 总体空间复杂度为 (O(N + M) = O(N))。