# shortest cycle passing through vertices a and b with changeable edge weights

given a weighted undirected graph with $N$ vertices $(N \leqslant 500)$ we start from vertex $S$ and wo go to $M$ and then we go to $T$ and then we return to $S$.

each edge in graph has weight $a_i$ at the beginning but after the first time we pass any edge that edge weight will become $b_i$. ($b_i \leqslant a_i$)

the task is to find the minimum sum of edges for this traverse.

time limit : 2 sec.

This is from Iran's IO, a contest that is finished. Source: https://quera.ir/course/assignments/4573/problems

• Doesn't simply applying common algorithms of finding shortest path like A* or Dijkstra algorithm three times work? Commented Mar 10, 2018 at 9:02
• i think i made counterexample for this idea. assume you have two shortest path from $S$ to $T$ with $a_i$ but one of them has shorter path of $b_i$ so it may be useful and be better for the next of cycle but we get in the longer one. Commented Mar 10, 2018 at 10:05
• We compute the shortest path from $S$ to $M$, then recompute the shortest path from $M$ to $T$ according to the new weights, and so on. What's the problem of this method? Commented Mar 10, 2018 at 10:17
• assume this as $a_i$ weights and vertex $0$ be $S$ and vertex $3$ be $M$and vertex $6$ be $T$ and this be $b_i$ weights then if you wrongly choose $0 -> 2 -> 3$ at your first dijkstra then your algorithm prints the wrong answer.am i right?! Commented Mar 10, 2018 at 10:39
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. I suggest editing the question to show us what approaches you've already considered and why you've rejected them.
– D.W.
Commented Mar 10, 2018 at 17:24

This solution assumes all weights are non-negative.

Lemma. There exists an optimal traverse with the following shape ($$A, B,C$$ may be the same vertex and may coincide with $$S,M,T$$), where each arrow represents a simple path, and paths represented by different arrows are edge-disjoint.

The strict proof of this lemma is somewhat tedious, so I omit it here (the idea is shown in another answer). If I have time in the future, I'll add it into this answer.

Let $$d_a(x,y), d_{a+b}(x,y)$$ respectively denote the shortest distance between vertexes $$x$$ and $$y$$ when edges have weights $$a_i$$'s and when edges have weights $$(a_i+b_i)$$'s. Let $$\mathrm{opt}$$ denote the value of optimal solution, then by this lemma we have

\begin{align*} \mathrm{opt}\ge\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\ &+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S). \end{align*}

On the other hand, following the shortest path (with weights $$a_i$$'s or $$(a_i+b_i)$$'s accordingly) from $$S$$ to $$A$$, then from $$A$$ to $$B$$, and so on, constitutes a valid traverse. Easy to see the cost of this traverse is no more than

\begin{align*} d_a(A, B)+d_a(B,C)+d_a(C,A)+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S), \end{align*}

so

\begin{align*} \mathrm{opt}\le\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\ &+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S). \end{align*}

As a result,

\begin{align*} \mathrm{opt}=\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\ &+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S). \end{align*}

So one can pre-compute the all-pair shortest paths using Floyd–Warshall algorithm, then exhaust all posible $$(A,B,C)$$'s to find $$\mathrm{opt}$$. This algorithm costs $$O(N^3)$$.

• Does your lemma assume that all edge weights are non-negative? I suspect it does. Unfortunately the question doesn't appear to guarantee that, and the poster hasn't responded yet to my question about whether we can assume that.
– D.W.
Commented Mar 12, 2018 at 19:26
• @D.W. Yes, it does. Commented Mar 13, 2018 at 2:02
• nice thanks:).nice idea.i got ACC :) and the edges are non negetive Commented Mar 13, 2018 at 18:27