P8914 [DMOI-R2] Dreamland.

Little A had a nightmare.

Little A’s dreamland can be seen as an undirected graph with $n$ nodes and $m$ edges. Little A is at node $S$, a monster is at node $B$, and the safe house is at node $F$. The monster is chasing Little A, and Little A needs to escape to the safe house. Little A realizes this is his own dream, so he can control it to some extent. He sets the monster’s moving speed to $3$, but the cost is that his own moving speed is set to $2$. Little A will always walk along a shortest path to $F$. If there are multiple shortest paths, Little A will choose the one whose **sequence of visited node indices in order is lexicographically smallest**, because he thinks this makes it least likely to be caught. The monster wanders in the dreamland. It moves randomly to a neighboring node, and it will not visit any node that it has already visited again. Now Little A needs to know **in the worst case** whether he can safely reach the safe house, or when he will be caught by the monster.

The first line contains five integers $n,m,S,B,F$. The next $m$ lines each contain three integers $u_i,v_i,w_i$, meaning there is an undirected edge of length $w_i$ between $u_i$ and $v_i$.

Two lines. If Little A **in the worst case** can safely reach the safe house, output `YES`, and then on the next line output the distance from the monster to the safe house after Little A arrives at the safe house. If Little A **in the worst case** cannot safely reach the safe house, output `NO`, and then on the next line output when Little A is caught by the monster. If the answer on the second line is an integer, output the integer; **otherwise output a decimal**.

**Explanation of “worst case”**: The monster may have multiple possible ways to move. In other words, you need to consider every possible way the monster can move. As long as there exists some shortest-path movement strategy of the monster that can catch Little A, the answer is `NO`. The worst case means the monster chooses, among all its possible strategies, the one that can catch (or get close to) Little A the fastest. Also, this problem does not have a special judge. That is, if the answer is an integer, you must output it exactly as an integer, without a decimal point. The testdata guarantees that there will be no answer with more than two decimal places. ### Constraints This problem uses bundled testcases. $$ \def\arraystretch{1.5} \begin{array}{c|c|c|c|c}\hline \textbf{~~Subtask~~}&\bm{~~n \le ~~}&\bm{~~~~m \le~~~~}& ~\textbf{~~Special Property~~}~&\textbf{~~Score~~}\cr\hline 0 &10 &20 & &10\cr\hline 1 &500 &1000 & &10\cr\hline 2 &800 &2000 & &10\cr\hline 3 &2\times10^5& &\text{A+B}&15 \cr\hline 4 &2\times10^5& &\text{A}&15 \cr\hline 5 &10^5 &2\times10^5& &20\cr\hline 6 &2\times10^5&2\times10^5& &20 \end{array} $$ Special property $\text{A}$: $m=n-1$. Special property $\text{B}$: for each given $v_i$, it satisfies $v_i=u_i+1$. For $100\%$ of the data, it is guaranteed that $S \ne B \ne F$ and $1 \le S,B,F \le n$, $1 \le w_i \le 10^3$, the graph is connected, and there are no multiple edges. ### Special Scoring Method This problem uses subtask dependencies, as follows: - For subtasks $i\in\{0,3\}$, you only need to solve subtask $i$ correctly to obtain the score of subtask $i$. - For subtask $4$, you need to solve subtask $3$ correctly to obtain the score of subtask $4$. - For subtasks $i\in\{1,2,5,6\}$, you need to solve subtask $0$ correctly to obtain the score of subtask $i$. ### Attachment Note Since many contestants got stuck on sub3 during the contest, a set of testdata within sub3 is provided here to help you check and fix your code. Translated by ChatGPT 5