Strict Triangle

The condition in the statement looks like equality, but because shortest paths obey triangle inequality, it is really asking for

$$\mathrm{dist}(1,n)<\mathrm{dist}(1,k)+\mathrm{dist}(k,n).$$

So we need to make every shortest $1\to n$ path avoid $k$ in a strict way. No ties allowed. Ties are death here.

Step 1: push weights to the extremes

Suppose some valid assignment works. Let $P$ be a shortest path from $1$ to $n$ under that assignment.

We can transform the assignment like this:

• every edge on $P$ becomes green: weight $l_i$;
• every edge outside $P$ becomes red: weight $r_i$.

This keeps the answer working.

Why? If we decrease an edge on $P$, then the chosen shortest $1\to n$ distance decreases by exactly that amount. Meanwhile, $\mathrm{dist}(1,k)+\mathrm{dist}(k,n)$ can decrease by at most that amount. Intuitively, an edge of a simple $1\to n$ path cannot be useful in both halves through $k$ in a way that gives a double discount; shortest-path geometry blocks that nonsense.

If we increase an edge outside $P$, then the path $P$ is untouched, so $\mathrm{dist}(1,n)$ does not increase, and the through-$k$ distance cannot decrease.

Therefore, we only need to decide whether there exists a path $P$ such that setting $P$ to lower bounds and all other edges to upper bounds gives strict inequality.

Step 2: characterize a good path

Fix a candidate path $P$ from $1$ to $n$. Let $\ell_P(u,v)$ be the lower-bound length of the segment of $P$ from $u$ to $v$, where $u$ appears before $v$ on $P$.

Also define

$$d[x]=\mathrm{dist}_R(x,k),$$

where every edge has weight $r_i$.

The path $P$ is good exactly when for every pair $u,v$ on $P$ with $u$ before $v$,

$$\ell_P(u,v)<d[u]+d[v].$$

The right side is the best possible upper-bound cost of going from $u$ to $k$ and then from $k$ to $v$.

Why is this condition necessary? If for some $u,v$ we had

$$\ell_P(u,v)\ge d[u]+d[v],$$

then the segment of $P$ from $u$ to $v$ could be replaced by a route through $k$ of no larger length. That creates a shortest $1\to n$ path through $k$, so equality holds. Bad.

Why is it sufficient? If a shortest $1\to n$ path through $k$ existed, look at the last vertex of $P$ it touches before reaching $k$, and the first vertex of $P$ it touches after leaving $k$. Between those two vertices, the through-$k$ route would be no longer than the corresponding segment of $P$, violating the condition above.

So the whole problem becomes: find a path from $1$ to $n$ whose every segment beats the cops going through $k$.

Step 3: the robber interpretation

Think of yourself as a robber walking from $1$ to $n$.

• You traverse edge $i$ in $l_i$ seconds.
• Citizens and cops travel using edge time $r_i$.
• Whenever you visit a city $v$, someone from $v$ starts running to the police station $k$.
• Once the cops are warned, they can run from $k$ toward you.

For a city $v$, the warning time from $v$ to $k$ is $d[v]$.

At your current city, define a timer $t$:

• if $t<0$, cops will be warned in $-t$ seconds;
• if $t\ge 0$, cops were warned $t$ seconds ago.

You are safe at vertex $v$ exactly when

$$t<d[v].$$

If $t\ge d[v]$, the cops have had enough time to get from $k$ to $v$, so you are caught. Skill issue, but for the path, not for you.

Step 4: timer transition

At vertex $u$ with timer $t$, traverse edge $(u,v)$ with lower weight $l$.

During the move, time increases by $l$, so the old warning timer becomes $t+l$.

But when you arrive at $v$, a new citizen from $v$ can warn the cops after $d[v]$ seconds. Relative to the current time, that new warning timer is $-d[v]$.

The cops use the earliest warning, which corresponds to the larger timer, so

$$t' = \max(t+l, -d[v]).$$

This is the whole trick.

We want the minimum possible timer for each vertex. Smaller timer means safer. Since every transition strictly increases time by a positive edge length, we can process states in increasing timer order, just like Dijkstra.

Algorithm:

1. Run Dijkstra from $k$ using weights $r_i$ to compute $d[v]$.
2. Start a modified Dijkstra from vertex $1$ with timer $$t_1=-d[1].$$
3. Pop the state with smallest timer.
4. If $t\ge d[u]$, skip it: you are caught at $u$.
5. Otherwise, process $u$ and relax every edge with $$nt=\max(t+l_i,-d[to]).$$
6. If vertex $n$ is processed safely, answer YES; otherwise NO.

The complexity is

$$O((n+m)\log n)$$

per total graph size, which is fine because the sums of $n$ and $m$ are both bounded by $2\cdot 10^5$.