CF-2128F · Welcome to the Sunny Side!

This problem is somewhere in my top-5 problems for 2025. The solution is surprisingly simple and intuitive for a 3200 rated problem.

Problem CF-2128F

Statement

You are given an undirected connected graph with $n$ nodes and $m$ edges. The weight wi of the $i$ -th edge is not yet decided and must be a real number between $l_{i}$ and $r_{i}$ .

You are given a node $k$ . Determine if there exists a valid assignment of weights $(w_{1}, \dots, w_{m})$ such that:

$l_{i} \leq w_{i} \leq r_{i}$ for all $i$

${dis}_{w} (1, n) \neq {dis}_{w} (1, k) + {dis}_{w} (k, n)$

Constraints:

$4 \leq n \leq 200000$
$n - 1 \leq m \leq 200000$
$2 \leq k \leq n - 1$
no self-loops
$1 \leq l_{i} \leq r_{i} \leq 10^{9}$

Solution

It's easy to see that the problem requires us to check if there exists an assignment of weights for which the node $k$ doesn't lie on any shortest path from $1$ to $n$ . Alternatively, the shortest path from $1$ to $n$ must have a strictly smaller total weight than the shortest path from $1$ to $n$ which contains the node $k$ .

Let's consider some shortest path in a valid assignment of weights $w$ and play around with the weight relations (with the hope of simplifying things). Let's consider a particular shortest path $P$ containing the edges indexed $e_{1}, e_{2} \dots e_{p}$ (this will obviously (a) be a simple path with no repeated edges or nodes (b) not contain the node $k$ ).

Observation 1:

For all $e_{i} \notin P$ , we can set $w_{e_{i}} = r_{e_{i}}$ without affecting the validity of $w$ .

Proof

Doing so doesn't affect the weight of $P$ and only potentially increases the weight of the paths from $1$ to $n$ which go through $k$ . Since the shortest one amongst the latter was strictly worse than $P$ before these changes, the shortest one amongst the latter after these changes is also strictly worse.

Observation 2:

For all $e_{i} \in P$ , we can set $w_{e_{i}} = l_{e_{i}}$ without affecting the validity of $w$ .

Proof

Consider a single change, on edge $e_{i}$ . Let's say performing this change results in its weight decreasing by $△$ . This results in the total weight of $P$ decreasing by exactly $△$ (since $P$ contains no repeated edges). We want to show that there can exist no shortest path through $k$ after this change. Paths from $1$ to $n$ through $k$ can be classified into three categories:

Paths that don't contain the edge $e_{i}$ : they were worse than $P$ , and remain so.
Paths that contain the edge $e_{i}$ once: they were initially worse than $P$ , and their total edge weight is reduced by the same amount as $P$ , so they remain worse.
Paths that contain the edge $e_{i}$ multiple times: while they receive a greater decrease to their total weight than $P$ , simply cannot be the shortest paths from $1$ to $n$ as they're not simple, and all edge weights are strictly positive.

A vague skeleton for a potential solution begins to take form: maybe we fix some simple path from $1$ to $n$ , set the weights of all edges on it to $l_{e_{i}}$ , all outside it to $r_{e_{i}}$ , and check if:

It's the shortest path from $1$ to $n$ .
Its total weight is strictly smaller than that of the shortest path from $1$ to $n$ through $k$ .

We can observe that the first condition is actually unnecessary: it suffices to check for the second condition, because the second being satisfied implies that there's some path from $1$ to $n$ with strictly smaller total weight than the shortest one through $k$ . For now, continue to assume that $P$ is a shortest path from $1$ to $n$ .

Let us now look at the intersection between $P$ and the shortest path from $1$ to $n$ through $k$ , $P^{'}$ .

This leap might feel a bit arbitrary to the passive reader, so the intuitive justification I provide is that since we reach nodes on $P$ in an optimal manner w.r.t. $1$ and $n$ , (for any shortest path from $s$ to $t$ , the path from $s$ to any intermediate node $p$ is one of the shortest paths from $s$ to $p$ , and the path from $t$ to any intermediate node $p$ is one of the shortest paths from $t$ to $p$ ), and that $P$ and $P^{'}$ necessarily intersect at their extremes ( $1$ and $n$ ), one needs to "deviate" from $P^{'}$ only to visit $k$ . A more formal justification follows.

Let the vertices on $P^{'}$ be $v_{1}, v_{2}, \dots v_{q}$ . Define $f (u)$ to be $1$ if the node $u$ lies on $P$ , and $0$ otherwise.

Observation 3:

There exists some $P^{'}$ (shortest path from $1$ to $n$ through $k$ ) such that the sequence $S (P^{'}) = f (v_{i}) : 1 \leq i \leq q$ takes the following form: $11 \dots 1100 \dots 0011 \dots 11$ (ie. a non-empty segment of $1$ s, followed by a non-empty segment of $0$ s, followed by a non-empty segment of $1$ s).

Proof

$S (P^{'})_{1} = 1$ as $v_{1} = 1, f (1) = 1$ .
$S (P^{'})_{q} = 1$ as $v_{q} = n, f (n) = 1$ .
There exists some $j \in (1, q)$ such that $v_{j} = k$ , and $S (P^{'})_{j} = 0$ as $f (k) = 0$ .
Let us now consider some shortest path from $1$ to $n$ through $k$ , $R$ and show that we can transform $R$ to $P^{'}$ while still having the same weight.

The first three points imply that the sequence $S (R)$ looks like $1 \dots [arbitrary mix of 0s and 1s] 0 [arbitrary mix of 0s and 1s] 1$ (with the guaranteed $0$ at position $j$ existing due to the guaranteed (and singular) existence of $k$ in $R$ ). Now consider the closest $1$ s to $S (R)_{j}$ to the left and right (both are guaranteed to exist as the first and last elements are $1$ s). Let their position be $l$ and $r$ respectively. Let the $l$ -th and $r$ -th nodes in $R$ be $g$ and $h$ respectively.

Let's now construct the following path, $R^{'}$ :
1. We go from $1$ to $g$ through the same sub-path we do on $P$ (note that $g$ is guaranteed to exist in $P$ ).
2. We go from $g$ to $h$ through the same sub-path we do on $R$ (note that this ensures we go through $k$ ).
3. We go from $h$ to $n$ through the same sub-path we do on $P$ (note that $h$ is guaranteed to exist in $P$ ).
Claim 3.1:

The total weight of $R^{'}$ is not greater than that of $R$ .

Proof:

Consider the three subpaths that both $R$ and $R^{'}$ can be divided into: $1 \to g \to h \to n$ . The second sub-path ( $g \to h$ ) is the same in both $R$ and $R^{'}$ , and therefore has an equal contribution to the weight. Now, since $P$ is one of the shortest paths from $1$ to $n$ , the sub-paths $1 \to g$ and $h \to n$ on $P$ are the shortest paths between those nodes, and therefore cannot have greater weights than their counter-parts in $R$ .

Claim 3.2:

$S (R^{'}) = f (v_{i}) : 1 \leq i \leq q$ takes the following form: $11 \dots 1100 \dots 0011 \dots 11$ (ie. a non-empty segment of 1s, followed by a non-empty segment of 0s, followed by a non-empty segment of 1s).

Proof:

Obvious.

We have therefore showed the existence of a valid $P^{'}$ .

Fuck, I now feel stupid for putting the proof above into a spoiler as I'm going to be using terms defined therein. Just read it if you haven't.

Anyways, how does all of this even help us? It helps us because it implies that if there exists a valid assignment of weights, then there exists a pair of paths $P, P^{'}$ (and the implicit assignment of weights $w$ defined by $P$ as mentioned above) such that:

$P$ is the shortest path from $1$ to $n$ .
$P^{'}$ is the shortest path from $1$ to $n$ through $k$ , and satisfies that nice property we derived earlier (follows $P$ , only deviates once to visit $k$ , and then follows $P$ again).
$P$ has a smaller total weight than $P^{'}$ .

This is extremely convenient as we can now look at the smallest path from $1$ to $n$ through $k$ by only considering the previously defined $g$ and $h$ on $P$ .

Let's now define $d_{k} (u)$ to be the shortest distance between $u$ and $k$ when all the edge weights are set to $r_{e_{i}}$ .

We observe that for a fixed $P$ , the shortest path from $1$ to $n$ through $k$ has the weight:

$\min_{g, h \in P}(\text{dis}_w(1, g) + d_k(g) + d_k(h) + \text{dis}_w(h, n))$

The only point of contention one may have with this formula is that for certain $g$ (or symmetrically $h$ ), $d_{k} (g)$ may not actually represent the shortest distance between $g$ and $k$ in the current path, as some edge weights set to $r_{e_{i}}$ in the graph $d_{k}$ is derived from may lie on $P$ here and consequently be set to $l_{e_{i}}$ .

Observation 4:

The minimum for $(1)$ is produced by at least one pair $g, h$ for which both $d_{k} (g)$ and $d_{k} (h)$ are valid.

Proof

As we've already shown earlier, some optimal path through $k$ is going to travel along $P$ for some prefix, hop off it once, visit $k$ , and hop back onto $P$ for the remaining suffix. Those two "hop points" can be chosen as $g$ and $h$ to get the minimum for $(1)$ .

Let's simplify things a bit for us now.

Observation 5

If $(1)$ is satisfied for any path $P$ without $k$ , then the weight assignment induced by $P$ is valid.

Proof

Exercise for the reader. Just examine the places where we used the fact that

P

was a shortest path until now, and realize that we can make do with weaker claims.

How does this relate to our original requirement of having $P$ be strictly shorter than $P^{'}$ ? We now require:

$\min_{g, h \in P}(\text{dis}_w(1, g) + d_k(g) + d_k(h) + \text{dis}_w(h, n)) > \text{dis}_w(1, n)$ $\implies d_k(g) + d_k(h) > \text{dis}_P(g, h) \quad \forall g, h \in P \tag{1}$

${dis}_{P} (g, h)$ just refers to the distance between $g$ and $h$ on $P$ here.

Alright, with all of that foreplay out of the way, how do we design an efficient algorithm that exploits these properties? All we care about is finding a path $P$ in the graph such that $(1)$ is satisfied for it.

Consider a simple line graph from $1$ to $n$ . How would we check if the unique path from $1$ to $n$ satisfies $(1)$ ? Let's obviously assume that $d_{k}$ has been precomputed.

Consider the following pseudo-code that does this:

p = nodes on the path from 1 to n
sat = true

for i from 1 to n:
    v = p[i]
    for j from 1 to i:
        u = p[j]
        if dk[u] + dk[v] <= dis_P(u, v):
            sat = false

This works in $O (n^{2})$ (forget about the precomputation for now), but can we do better? We realize that the distance function ${dis}_{P} (u, v)$ has a rather "continuous" nature, and we can exploit this to do something similar to kadane's algorithm (just maintain the value of the extreme suffix).

This leads to the following $O (n)$ solution:

p = nodes on the path from 1 to n
sat = true
worst_suffix = -dk[p[1]]

for i from 2 to n:
    v = p[i]
    worst_suffix = max(worst_suffix + dis_P(p[i - 1], v), -dk[v])
    if dk[v] <= worst_suffix:
        sat = false

Alright, let's now consider doing this for arbitrary paths in a general graph.

We will try to incrementally build good paths from node $1$ that have the potential to satisfy $1$ . What properties must such a potential path from $1$ to $u$ satisfy?

It must not contain $k$ .
$(1)$ must obviously be satisfied for $g, h$ on this prefix path.
In addition, note that as long as $(1)$ is satisfied on this prefix, the only thing that will affect $(1)$ as we further extend this path is the analogous value of worst_suffix until now. It's easy to see that we should aim to minimise this value.

This trivially leads to the following $O (n \cdot m)$ algorithm (just have $n$ rounds (max number of nodes in $P$ ) where you try to transition across every edge).

precompute dk using djikstras

opt[n]

opt[1] = -dk[1]
for u from 2 to n:
    opt[u] = inf

for round from 1 to n:
    nopt = opt
    for u from 1 to n:
        for [v, l, r] in adj[u]:
            if (u != k and v != k and dk[v] > opt[u] + l)
                nopt[v] = min(nopt[v], max(-dk[v], opt[u] + l))
    opt = nopt

if opt[n] != inf:
    valid assignment exists

To optimize this to $O ((n + m) \log n)$ , we can simply observe that we can use a Djikstra's like approach here due to the monotonic nature of the transitions (due to strictly positive edge weights).