Собственно, задача такова:
Дан неориентированный взвешенный граф. Для каждой вершины найдите длину кратчайшего простого цикла, проходящего через данную вершину.
Быстрейшее решение, что у меня есть, работает за N^4
→ Обратите внимание
До соревнования
Codeforces Round при поддержке NEAR (Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
Codeforces Round при поддержке NEAR (Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 162 |
| 2 | maomao90 | 160 |
| 3 | adamant | 157 |
| 4 | maroonrk | 154 |
| 5 | -is-this-fft- | 150 |
| 6 | Petr | 148 |
| 6 | SecondThread | 148 |
| 8 | atcoder_official | 147 |
| 9 | TheScrasse | 145 |
| 9 | nor | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 16.07.2024 04:03:49 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been translated by Domonion (original revision, translated revision, compare)
are there negative edges?
seems like it's not. since it will make this problem NP-hard.
Решение за O(N3).
If O(n^3logn) is good enough, for each node, for each edge of the node, remove the edge, run dijkstras to find the distance from the node to the neighbor on the other side of the edge, and add the edge weight to it. The answer is the minimum of these.
Dijkstra's Algorithm does not run in O(N log(N)) time.
I think it's possible to do in
. To compute answer for vertex v, run Dijkstra from it then for every edge w suposse that this edge is included in some cycle of v in the way 
(where wA and wB are vertexes connected by edge w) and calculate its weight. Answer for v gonna be a minimum of these weights.
It's also O(n^3 log n)
No it's not. For each vertex you run dijkstra and check all edges so actually it is O(n * (m + mlogn)). Of course if there will be like n2 edges then it indeed gonna work in O(n3 * logn), but if such constraints exists then n should be quite small.
Your algorithm does not always compute simple cycles. Consider the cycle
, which is not a simple cycle, but is taken into account by your algorithm.
please ignore this :(
Won't work, the graph is undirected, so A[v][v] will be 2x the lightest outgoing edge from v.
omg i was stupid. Sorry for that
I don't know if this is a coincidence or not, but it seems you are not the only one solving this problem: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf