题解：「JOI 2024 Final T2」建設事業 2 / Construction Project 2（基于提供代码）

核心思路总览

本题是 图论最短路径 + 计数优化 问题，核心通过“预处理最短路径 + 排序二分计数”求解。先计算原图中起点 (S) 和终点 (T) 到所有节点的最短距离，再通过排序和二分快速统计满足条件的新建铁路线方案数，整体复杂度 (O((N + M) \log N))，适配 (N, M \leq 2 \times 10^5) 的规模。

关键背景与路径分析

1. 新增铁路线的作用

新建铁路线 (u-v)（花费 (L)）后，从 (S) 到 (T) 的最短路径可能通过该铁路线，形式为： [ S \to \dots \to u \xrightarrow{L} v \to \dots \to T \quad \text{或} \quad S \to \dots \to v \xrightarrow{L} u \to \dots \to T ] 其总花费为 (\min(sd[u] + L + td[v], sd[v] + L + td[u]))，其中：

• (sd[x]) 是原图中 (S) 到 (x) 的最短距离。
• (td[x]) 是原图中 (T) 到 (x) 的最短距离。

2. 合法方案的条件

若原图中 (S) 到 (T) 的最短距离已 (\leq K)，则所有 (\frac{N(N-1)}{2}) 种方案均合法。否则，需满足： [ sd[u] + td[v] + L \leq K \quad \text{或} \quad sd[v] + td[u] + L \leq K ] 由于 (u < v) 且上述两式对称，可简化为统计满足 (sd[u] + td[v] + L \leq K) 的 ((u, v)) 对数（因 ((u, v)) 和 ((v, u)) 仅算一次，且排序后可统一处理）。

核心状态与数组定义

完整代码（带关键注释）

#include <bits/stdc++.h>
#define inl inline
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, IB = 1 << 21;

// 快速读入优化（适配大数据量）
char IN[IB], *IS = IN + IB, *IT = IS;
#define getchar() (IS==IT&&(IT=IN+fread(IS=IN,1,IB,stdin)),IS==IT?EOF:*IS++)

// 边的结构：目标节点y，权重w
struct E {
    int y;
    ll w;
};
vector<E> e[N];

// 优先队列元素：距离d，节点u（用于Dijkstra算法，小根堆）
struct Q {
    ll d;
    int u;
    inl bool operator <(Q t) const {
        return d > t.d;  // 重载小于号，使优先队列按距离升序排列
    }
};
priority_queue<Q> q;

int n, m, S, T;
ll an, L, K, sd[N], td[N];  // sd: S到各点距离；td: T到各点距离

// 快速读入函数
inl ll Read() {
    ll s = 0;
    char c;
    while (!isdigit(c = getchar()));  // 跳过非数字字符
    for (; isdigit(c); c = getchar())
        s = s * 10 + c - '0';
    return s;
}

int main() {
    // 读入输入参数
    n = Read();
    m = Read();
    S = Read();
    T = Read();
    L = Read();
    K = Read();

    // 构建邻接表
    for (int x, y, w; m--;) {
        x = Read();
        y = Read();
        w = Read();
        e[x].push_back({y, w});  // 双向边
        e[y].push_back({x, w});
    }

    // 第一步：Dijkstra算法计算S到所有节点的最短距离sd
    memset(sd, 63, sizeof(sd));  // 初始化距离为无穷大（0x3f3f3f3f3f3f3f3f）
    sd[S] = 0;
    q.push({0, S});
    while (!q.empty()) {
        ll d = q.top().d;
        int u = q.top().u;
        q.pop();
        if (d > sd[u]) continue;  // 跳过非最短路径的冗余节点
        for (E v : e[u]) {  // 遍历所有邻边
            if (d + v.w < sd[v.y]) {  // 松弛操作
                sd[v.y] = d + v.w;
                q.push({sd[v.y], v.y});
            }
        }
    }

    // 特判：若原图中S到T的距离已<=K，则所有方案均合法
    if (sd[T] <= K) {
        printf("%lld\n", n * (n - 1ll) / 2);  // 总方案数为N*(N-1)/2
        return 0;
    }

    // 第二步：Dijkstra算法计算T到所有节点的最短距离td
    memset(td, 63, sizeof(td));  // 初始化距离为无穷大
    td[T] = 0;
    q.push({0, T});
    while (!q.empty()) {
        ll d = q.top().d;
        int u = q.top().u;
        q.pop();
        if (d > td[u]) continue;  // 跳过非最短路径的冗余节点
        for (E v : e[u]) {  // 遍历所有邻边
            if (d + v.w < td[v.y]) {  // 松弛操作
                td[v.y] = d + v.w;
                q.push({td[v.y], v.y});
            }
        }
    }

    // 第三步：排序sd和td数组，用于二分计数
    sort(sd + 1, sd + n + 1);  // 排序S到各点的距离
    sort(td + 1, td + n + 1);  // 排序T到各点的距离

    // 第四步：双指针法统计合法方案数
    for (int i = 1, j = n; i <= n && j; ++i) {
        // 对于每个sd[i]，找到最大的j使得sd[i] + td[j] + L <= K
        while (j && sd[i] + L + td[j] > K) {
            --j;
        }
        an += j;  // 累加合法的v的数量（td[1..j]均满足条件）
    }

    // 输出结果
    printf("%lld\n", an);
    return 0;
}

核心流程拆解

1. 最短路径计算

• Dijkstra算法：分别从 (S) 和 (T) 出发，计算到所有节点的最短距离 (sd) 和 (td)。因边权非负，Dijkstra 算法结合优先队列可高效求解，时间复杂度 (O((N + M) \log N))。
• 特判优化：若原图中 (S) 到 (T) 的最短距离已 (\leq K)，则无需新建铁路线即可满足条件，所有 (\frac{N(N-1)}{2}) 种方案均合法，直接输出结果。

2. 合法方案计数

• 排序预处理：将 (sd) 和 (td) 数组排序，为后续二分查找做准备。
• 双指针法：对于排序后的 (sd[i])，通过双指针找到最大的 (j) 使得 (sd[i] + td[j] + L \leq K)，则 (td[1..j]) 均满足条件，累加 (j) 即得当前 (i) 对应的合法方案数。总计数复杂度 (O(N \log N))（排序）( + O(N))（双指针）。

关键难点解析

1. 路径简化与对称性利用

新建铁路线 (u-v) 的两种可能路径（(u \to v) 和 (v \to u)）可通过 (sd[u] + td[v]) 和 (sd[v] + td[u]) 表示，但由于 (u < v) 且数组已排序，双指针法统计的结果已包含所有对称情况，无需重复计算。

2. 大数据量优化

• 快速读入：使用字符数组批量读入，避免标准输入的性能瓶颈。
• Dijkstra优化：通过优先队列和松弛操作的判断（d > sd[u]），跳过冗余节点，提升效率。
• 双指针替代二分：相比对每个 (i) 执行二分查找（(O(N \log N))），双指针法将计数复杂度降至 (O(N))，进一步优化性能。

复杂度分析

• 时间复杂度：(O((N + M) \log N + N \log N))，其中 Dijkstra 算法占 (O((N + M) \log N))，排序占 (O(N \log N))，双指针计数占 (O(N))。
• 空间复杂度：(O(N + M))，用于存储邻接表和最短距离数组。

该方案高效适配 (N, M \leq 2 \times 10^5) 的数据规模，核心通过预处理最短路径和排序优化计数，避免了直接枚举的 (O(N^2)) 复杂度。