| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Given a weighted, undirected graph. How I can find 2 paths from S to T, such that they don't share any edge (but may share some nodes), and sum of their lengths must be minimal possible ??
Edit: The problem has been solved using Minimum-cost flow. Thanks for Govikhuu
It is mincost-maxflow problem. All edge must have 1 unit capacity and edge weight is cost of using that edge. Then you can simply find minimum cost of 2 unit flows.
Can you explain your algorithm in more details please ?
It is a problem from the running contest — Bubble Cup. Link
I don't know any thing about this contest. I'm trying to solve this problem from UVa (10806 — Dijkstra, Dijkstra.).
That was my first thought. Even if he's truly not solving that problem, I think waiting before posting the solution would be nice. I'm sure there are quite a few people here on Codeforces that participate in BubbleCup.
Excuse me, I appreciate your opinion. :) But I want to continue my practice and solve this problem! Any one who are participating in this contest must be honest with himself and try to solve the problems without any cheating.