P10970 PKU ACM Team's Excursion [No Data Yet]

Source: .

The PKU ACM team has a traditional activity: going hiking during the summer camp. However, this tradition has been put on hold for several years. To revive this meaningful and fun tradition, the coach is planning an excursion for this summer. Also, the new team members strongly request going to an “exciting” place. To satisfy their wish, the coach found a national park and obtained its map. On the map, there are $n$ intersections (numbered from $0$ to $n-1$) connected by $m$ directed roads. The map has an interesting property: once you leave the intersection you are currently at, you can never return to it. Therefore, this map is a typical directed acyclic graph (DAG). So why is this place exciting? Because some roads are called “bridges” (they are not real bridges, but special roads we will define), and they are dangerous because these “bridges” may collapse when we cross them. Do not panic. The safety facilities are sufficient and solid, so there is no physical danger, only psychological impact. Have fun! The hike will start from some starting intersection $s$ and end at some destination intersection $t$. You can find a route from intersection $s$ to $t$. A road is called a “bridge” if and only if once it disappears, you can no longer find a route from the starting intersection to the destination intersection. Other normal roads are not “bridges”, so they are not dangerous at all. According to hikers’ experience, the danger level of a “bridge” equals its length. Some pranksters want to make the hike more dangerous. But wait, a girl is crying. What? A girl? Finally, the PKU ACM team recruited a female member this year. Well... “Ladies first” is a long-standing policy of the PKU ACM team. The boys and the girl finally reached a compromise and decided to keep the hike as safe as possible. The national park provides a “fast” service. Hikers can book at most two buses in advance to help them avoid some of the most dangerous routes. Each bus can start from anywhere in the park (any intersection or any point on a road). However, the buses are powered by electricity, so each bus can travel continuously for no more than $q$ meters, and passengers must get off before the power runs out. Simply put, the team may choose two “fast” routes (each route can start anywhere and end anywhere), but the length of each route must not exceed $q$ meters. When the team takes a bus, the danger level along that segment can be ignored. The problem is reduced to finding a route from the start intersection to the destination intersection with the minimum total danger level. Along the way, we can take buses twice to make the route safer. The two bus routes can start anywhere and end anywhere, but the whole team must take one bus together each time. Individual actions are forbidden.

The first line contains an integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case: The first line contains five integers $n$, $m$, $s$, $t$, and $q$ ($1 \leq n \leq 100\,000$, $1 \leq m \leq 200\,000$, $0 \leq s$, $t < n$, $s \neq t$, $1 \leq q \leq 1\,000\,000\,000$), representing the number of intersections, the number of roads, the starting intersection, the destination intersection, and the maximum distance a single bus can travel. The next $m$ lines contain all road information in the DAG. Each line contains a triple $(u,v,w)$, meaning there is a road from intersection $u$ to intersection $v$ with length $w$ meters ($1 \leq w \leq 1\,000$).

For each test case, output one line containing an integer, the total danger level of the optimal route. If there is no route from $s$ to $t$, output -1.

Translated by ChatGPT 5