题目核心思路

本题要求在DAG中判断是否存在从1到$f_i$的路径，使得路径实际长度$x$满足 $r_i \leq x \leq \frac{p}{p-1} \cdot r_i$。核心思路是：

1. 利用DAG的拓扑序特性（边从小编号指向大编号），按节点编号从小到大处理；
2. 对每个节点维护可行的路径长度集合（用区间/有序集合存储）；
3. 查询时只需检查目标节点的可行集合是否与$[r_i, \frac{p}{p-1} \cdot r_i]$有交集。

关键优化

• 由于$d_i$和$r_i$数值极大（$10^{11}/10^{17}$），无法直接枚举长度，需用有序集合+区间合并维护每个节点的可行长度范围；
• 利用DAG的拓扑序（节点编号递增），无需额外拓扑排序，直接按编号处理即可。

C++ 代码实现

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

// 对每个节点维护可行的长度区间（左闭右闭），按左端点排序
vector<set<pll>> node_intervals;
vector<vector<pair<int, ll>>> adj; // 邻接表：adj[u] = [(v, d)]

// 合并区间：将[L, R]插入到s中，并合并重叠/相邻区间
void insert_interval(set<pll>& s, ll L, ll R) {
    if (L > R) return;
    // 找到第一个左端点 > R 的区间的前一个
    auto it = s.upper_bound({R, 1e18});
    if (it != s.begin()) {
        --it;
        // 检查是否有重叠/相邻
        if (it->second >= L - 1) {
            L = min(L, it->first);
            R = max(R, it->second);
            s.erase(it);
        }
    }
    // 合并后续重叠区间
    while (true) {
        it = s.lower_bound({L, 0});
        if (it != s.end() && it->first <= R + 1) {
            R = max(R, it->second);
            s.erase(it);
        } else {
            break;
        }
    }
    s.insert({L, R});
}

// 检查区间集合s是否与[ql, qr]有交集
bool check_intersection(const set<pll>& s, ll ql, ll qr) {
    if (s.empty()) return false;
    // 找到第一个左端点 > qr 的区间的前一个
    auto it = s.upper_bound({qr, 1e18});
    if (it != s.begin()) {
        --it;
        // 检查该区间是否与[ql, qr]重叠
        if (it->second >= ql) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, m, q;
        ll p;
        cin >> n >> m >> q >> p;
        // 初始化
        adj.assign(n + 1, {});
        node_intervals.assign(n + 1, set<pll>());
        // 节点1的初始区间：只有长度0（从自己到自己）
        node_intervals[1].insert({0, 0});
        
        // 读入边
        for (int i = 0; i < m; ++i) {
            int v, w;
            ll d;
            cin >> v >> w >> d;
            adj[v].emplace_back(w, d);
        }
        
        // 按节点编号处理（DAG拓扑序）
        for (int u = 1; u <= n; ++u) {
            if (node_intervals[u].empty()) continue;
            // 遍历u的出边
            for (auto& e : adj[u]) {
                int v = e.first;
                ll d = e.second;
                // 将u的所有区间 +d 后插入v的区间
                for (auto& interval : node_intervals[u]) {
                    ll L = interval.first + d;
                    ll R = interval.second + d;
                    insert_interval(node_intervals[v], L, R);
                }
            }
        }
        
        // 处理查询
        string ans;
        ans.reserve(q);
        ll coeff_num = p;
        ll coeff_den = p - 1;
        for (int i = 0; i < q; ++i) {
            int f;
            ll r;
            cin >> f >> r;
            ll ql = r;
            ll qr = (r * coeff_num) / coeff_den; // 注意：整数除法向下取整（题目中是实数范围，向下取整不影响）
            // 检查是否有交集
            if (check_intersection(node_intervals[f], ql, qr)) {
                ans += '1';
            } else {
                ans += '0';
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

代码解释

1. 数据结构

• adj：邻接表，存储DAG的边（u→v，边长度d）；
• node_intervals：每个节点的可行路径长度区间集合（左闭右闭），用set维护以保证有序。

2. 核心函数

• insert_interval：将新区间插入集合，并合并重叠/相邻区间，保证集合内区间互不重叠；
• check_intersection：检查查询区间[ql, qr]是否与节点的可行区间有交集。

3. 处理流程

1. 初始化节点1的可行区间为[0, 0]（从1到1的路径长度为0）；
2. 按节点编号从小到大处理（DAG拓扑序），将每个节点的可行区间加上边长度后，插入到邻接节点的区间集合中；
3. 处理查询时，计算查询区间[r_i, (r_i*p)/(p-1)]，检查目标节点的区间集合是否与该区间有交集。

复杂度分析

• 时间复杂度：$O((m + q) \log K)$，其中$K$是每个节点的区间数量（实际中区间合并后$K$很小）；
• 空间复杂度：$O(n + m + K \cdot n)$，主要消耗在邻接表和区间集合。

注意事项

1. 整数除法精度：(r*p)/(p-1) 是向下取整，由于题目中是实数范围，向下取整不影响结果（若严格相等则包含，否则不影响）；
2. 数据范围：必须用long long存储所有长度和查询值；
3. 多组数据：每次处理完一组数据后，需清空邻接表和区间集合。

该代码能高效处理题目中的数据范围（$\sum n,m,q \leq 5e5$），且通过区间合并避免了大数枚举的问题。