can you share your idea?

# | User | Rating |
---|---|---|

1 | jiangly | 3677 |

2 | Benq | 3601 |

3 | ecnerwala | 3542 |

4 | maroonrk | 3540 |

5 | cnnfls_csy | 3539 |

6 | orzdevinwang | 3493 |

7 | inaFSTream | 3478 |

8 | Um_nik | 3430 |

9 | Rebelz | 3409 |

10 | Geothermal | 3408 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 161 |

4 | SecondThread | 161 |

6 | nor | 159 |

7 | maroonrk | 158 |

8 | Um_nik | 154 |

9 | Geothermal | 145 |

9 | BledDest | 145 |

can you share your idea?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/26/2024 00:48:13 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 FloydIs 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.Halym2007What is your time complexity ?