P5872 [SEERC 2018] Rabbit vs Turtle

A rabbit and a turtle decide to race. Since the turtle is from Craiova and the rabbit is from Ardeal, the turtle runs much faster than the rabbit. Our goal is to help the rabbit win the race. The race takes place on a graph with $N$ nodes and $M$ edges. The race starts at node $1$ and ends at node $N$. Before the race, both the rabbit and the turtle choose a path that they will use during the race. Therefore, they know the graph and the time needed to traverse each edge. The turtle may be faster than the rabbit, but he is still a turtle (called George below). George will choose some nodes on his path to sleep for a while. If at some moment he finds out that the rabbit is cheating, George will stop sleeping until he finishes the race. The rabbit (called Stan below) has only one advantage: one of his great-great-great... grandmothers was a fox, so he also has a crafty side. Stan does not plan to follow his chosen path during the race (but George will follow his path). He plans to change his route at some node and then go directly to node $N$ via the shortest path. The only problem is that he must make a wise choice, because once George discovers that Stan is cheating, George will no longer sleep, which is unfavorable. Stan can change his route only after arriving at a node (he cannot change while moving along an edge). He does not know George’s sleeping plan, but you do. Compute how many nodes allow Stan to change his route and win the race. When Stan starts cheating, if George is not sleeping, he will notice immediately. If George is sleeping at that moment, he will notice only when he wakes up.

The first line contains two integers $N$ and $M$. The next $M$ lines describe the edges in the format $(A,B,T,R)$: there is an edge connecting nodes $A$ and $B$, the turtle needs $T$ time to traverse this edge, and the rabbit needs $R$ time. The edges are numbered from $1$ to $M$ in the input order. The next line contains an integer $P_T$, the number of edges in George’s path. The next $P_T$ lines describe the path as (edge id, sleep time): the path uses the edge with the given id, and after traversing this edge, George will sleep for a while, with the given sleep time. The sleep time after the last edge is meaningless, because George has already reached the finish. The next line contains an integer $P_R$, the number of edges in Stan’s initially chosen path. The last line contains $P_R$ integers, the edge ids of the edges in Stan’s initial path.

Output on the first line an integer $x$, the number of nodes where Stan can start cheating (i.e., the node where he starts cheating). On the second line output $x$ integers in increasing order, the ids of the nodes where Stan can start cheating.

- $2 \leq N \leq 100,000$. - $1 \leq P_R, P_T < 100,000$. - $1 \leq M \leq 200,000$. - $1 \leq T,R \leq 1,000,000,000$. - $0 \leq$ sleep time $\leq 1,000,000,000$. - The testdata guarantees that the edges on the race paths are described in the correct order (i.e., the end of one edge is the start of the next). - The testdata guarantees that the nodes on the turtle’s path do not repeat. - The testdata guarantees that the nodes on the rabbit’s path do not repeat. - If the rabbit and the turtle arrive at the finish at the same time, the rabbit is considered to win. - If the rabbit starts cheating exactly when the turtle starts sleeping, then the turtle will fall asleep and will notice the cheating only when he wakes up. - The rabbit is considered cheating if and only if he changes his path and the new path is strictly faster than the original path (otherwise there is no need to cheat). - The cheating path may share nodes with the original path. The only requirement is that when he starts cheating, the rabbit moves to a different next node than in the original path. In some cases, he may also return to a node he visited before. Translated by ChatGPT 5