0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Doesn't simply applying common algorithms of finding shortest path like A* or Dijkstra algorithm three times work? $\endgroup$ – xskxzr Mar 10 '18 at 9:02
  • $\begingroup$ 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. $\endgroup$ – Ali.Mollahoseini Mar 10 '18 at 10:05
  • $\begingroup$ 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? $\endgroup$ – xskxzr Mar 10 '18 at 10:17
  • $\begingroup$ 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?! $\endgroup$ – Ali.Mollahoseini Mar 10 '18 at 10:39
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 10 '18 at 17:24
0
$\begingroup$

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. 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)$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Mar 12 '18 at 19:26
  • $\begingroup$ @D.W. Yes, it does. $\endgroup$ – xskxzr Mar 13 '18 at 2:02
  • $\begingroup$ nice thanks:).nice idea.i got ACC :) and the edges are non negetive $\endgroup$ – Ali.Mollahoseini Mar 13 '18 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.