can you share your idea?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 08:39:39 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Dijkstra Algorithm for Each Vertex
Run Dijkstra from each vertex. While doing so, keep track of the shortest path to each other vertex.
When considering a new edge during the algorithm, if the edge leads to a vertex already visited, you have found a cycle. Calculate its length and compare it with the shortest cycle found so far.
what is your time complexity?
$$$O(EV\log V)$$$
Is there any way to find with MST(minimum spanning tree)?
Are you looking for something faster than $$$O(EV)$$$? If yes, that isn't possible with MST. Consider a graph where every edge has the same weight. Now the MST is just any spanning tree and it doesn't give you any extra info. This case can be solved in $$$O(EV)$$$ by replacing dijkstra with bfs since all edges have the same weight, but nothing faster is possible afaik.
thanks
thanks
You can also do this in O(V^3) using Floyd
Is there a less-than-O(V^3) approach, though?
Given a positive weighted undirected graph, find the minimum weight cycle in it. The idea is to use shortest path algorithm. We one by one remove every edge from the graph, then we find the shortest path between two corner vertices of it. We add an edge back before we process the next edge.Halym2007
What is your time complexity ?