思考题 with song

75

There have been 73 heroes failing to rescue the princess, and the 74-th was killed by the princess. As the 75-th knight, you decided to become stronger so that you would survive the princess's attack.
You are given a directed graph of N nodes and M edges. The Node #1 is your starting village and Node #N is the princess's castle. On node i there is one monster at Lvl X_i and Exp Y_i, meaning if you are at least X_i levels and are on the same node as the monster, you can beat it and gain Y_i levels. You can choose not to beat a monster at a node. You start with lvl Y_0
Can you reach node N with at least X_N levels?

Constriants

Standard: N,M<=500.
Lunatic: N,M<=100000
For all, 0\leq Y_i,X_i\leq 10^9

Solution

The author can only provide a solution for the standard testset. First do SCC decomposition. In each SCC we will discuss separately.
In each SCC, the process is like this: our knight fights all monsters he can fight, gain some level and repeat the process. If there is no monster he can fight, he will move on to the next SCC. So we need to find out when given the initial level what will the highest level the knight can achieve by walking around in the SCC.
Let's call the initial level Y.And this can be done by sorting all X_i in the SCC in ascending order. Then we call a monster reachable if X_i-\sum_{i=1}^{i-1}Y_i\leq Y. Then for any Y, the last monster we will fight in the SCC is the monster before the first unreachable monster that X_i\geq Y.
Proof: For each monster, it can be reached by two ways: 1. if the previous monster(don't forget we have sorted them) is reachable and X_i-\sum_{i=1}^{i-1}Y_i\leq Y. 2. if the previous monster is not reachable and X_i-\sum_{i=1}^{i-2}Y_i\leq Y. It can be seen that the second condition is nonsense, because X_{i-1}-\sum_{i=1}^{i-2}Y_i\gt Y and X_i\geq X_{i-1} holds, so X_i-\sum_{i=1}^{i-2}Y_i\gt Y always holds.
Then how to find out the first unreachable monster? We can store X_i-\sum_{i=1}^{i-1}Y_i in a segment tree and do segment tree descend. This task is trivial.
so we can construct a DP function DP(i,j) meaning if we are at the i-th SCC and at level j, what's the maximum level we can achieve when reaching the destination. Don't forget that after SCC Decomposition the graph is already a DAG. So DP works. Transferring is simple, DP(i,j) can move to all its neighbours with DP(nei,getMaxLv(i,j)). and in getMaxLv() we just simply call the segment tree.
Total complexity is O(NMlog) If there are any problems, please comment below. If you have better solutions, you can comment too!