P11082 [ROI 2019] High-Speed Tram (Day 1)

Translated from [ROI 2019 D1T3](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day1.pdf)。 The capital of Flatland needs to establish railway connections with nearby cities, and the existing railway system is already outdated. To optimize the railway system, a high-speed tram from the capital to another city needs to be launched. The Flatland railway network has a total of $n$ stations, numbered from $1$ to $n$, and the capital is station $1$. There are $m$ directed tracks between stations, and the travel time of each track is known.

The planning department wants to consider several different high-speed tram route plans. Each plan is defined by a destination station and an expected travel time. However, the department knows that the actual travel time may not fully match the expectation. Therefore, they use a parameter $p$ to evaluate whether a plan is feasible: for a given expected time $r$, if $r \le x \le \frac{p}{p-1} \times r$, where $x$ is the total travel time, then the route is considered feasible. Write a program that, given the description of the Flatland railway network and all route plans, determines whether there exists a feasible high-speed tram route for each plan.

The first line contains an integer $t$, the number of test cases. The following lines describe each test case. The first line of each test case contains four integers $n, m, q, p$, representing the number of stations, the number of tracks, the number of route plans to consider, and the allowed time deviation parameter. The next $m$ lines describe each track. Each line contains three integers $v_i, u_i, d_i$, representing the starting station, the ending station, and the travel time. The next $q$ lines describe each route plan. Each line contains two integers $f_i$ and $r_i$, representing the destination station and the expected travel time.

For each test case, output a string $s$ of length $q$ on one line. The $i$-th character $s_i$ equals $1$ if there exists a feasible high-speed tram route whose total travel time is within the interval $[r_i, \frac{p}{p-1} \times r_i]$; otherwise, $s_i$ equals $0$.

### Explanation of Sample $1$：  ### Explanation of Sample $2$：  For the first query, the route time is $1 + 120 + 1 = 122$, which meets the expectation. For the second query, the route time is $1 + 1 + 1 = 3$, which meets the expectation. For the fourth query, the route time is $70 + 1 + 1 = 72$, which meets the expectation. For the third and fifth queries, there is no feasible route that meets the expectation. ### Constraints： For $100\%$ of the data, $1 \le t \le 1000$, $1 \le v_i < u_i \le n \le 500000$, $1 \le m \le 500000$, $1 \le q \le 500000$, $2 \le p \le 20$, $1 \le d_i \le 10^{11}$, $2 \le f_i \le n$, $1 \le r_i \le 10^{17}$. Subtask scores and special properties: | Subtask | Score | $n$ | $m$ | $q$ | Other Special Properties | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $15$ | $n \le 10$ | $m \le 10$ | $q \le 10$ | | | $2$ | $24$ | $\sum n \le 5000$ | $\sum m \le 5000$ | $\sum q \le 5000$ | $r_i \le 5000$ | | $3$ | $17$ | | $m = 2n-2$ | $q \le 10$ | $p = 2$, and for each $i < n$, there are exactly two tracks from $i$ to $i+1$ | | $4$ | $11$ | | $m = 2n-2$ | | For each $i < n$, there are exactly two tracks from $i$ to $i+1$ | | $5$ | $11$ | $\sum n \le 1000$ | $\sum m \le 2000$ | | All $r_i$ values are equal | | $6$ | $11$ | | | | All $r_i$ values are equal | | $7$ | $11$ | | | | | Translated by ChatGPT 5