### minimario's blog

By minimario, history, 4 years ago,

Hi guys!

Does anyone have some problems that are modifications of Dijkstra's algorithm? I feel that the scope of Dijkstra problems I can solve is pretty small. Here are the types of problems I am referring to... (these are kinda easy)

1. 715B - Complete The Graph (precisely the type I want)
2. 449B - Jzzhu and Cities (really easy, but still a Dijkstra with modif)
3. 59E - Shortest Path
4. 2nd Shortest Path Problem (Find the 2nd shortest path from A to B)

Please, if somebody can provide some more (more difficult) Dijkstra problems, that would be really helpful!

• +48

 » 4 years ago, # |   +11 This problem.
•  » » 4 years ago, # ^ |   0 This problem was really fun! Thank you for your suggestion.
 » 4 years ago, # |   +29
•  » » 4 years ago, # ^ |   0 I solved the last one before, it's really amazing and unexpected!
•  » » » 3 years ago, # ^ |   0 Could you give a hint to the Sum problem..
•  » » » » 3 years ago, # ^ |   +8 Create a graph where the nodes are all possible remainders mod the smallest element of A.
•  » » » » » 3 years ago, # ^ |   0 Oh ok. thanks.
•  » » 7 months ago, # ^ | ← Rev. 3 →   0 the last link isn't working, any alternatives?
•  » » » 7 months ago, # ^ |   +1
 » 4 years ago, # |   0
 » 4 years ago, # |   -8 Kth shortest path problem. Not easy, but cool :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 What complexity do you want it? And does 1--2--1--2 count as a "path" between 1 and 2? (i.e., are cycles allowed in the path)Edit: AC'd with complexity . Is there better?
•  » » » 4 years ago, # ^ |   +2
•  » » » » 4 years ago, # ^ |   0 Can you provide a hint for this problem ?
•  » » » » » 4 years ago, # ^ |   0 SpoilerStore K shortest paths to each node and do dijkstra with those.
•  » » » » » 4 years ago, # ^ |   0 Here I explained how you can solve it. My code is here.
•  » » » 7 months ago, # ^ |   +8 There is a $O((n + k) \log m)$ algorithm. Its implementation uses a strange data structure. You can read it from here.
 » 4 years ago, # |   +16
 » 4 years ago, # |   +14 http://codeforces.com/problemset/gymProblem/100589/KInteresting problem IMO
•  » » 4 years ago, # ^ | ← Rev. 2 →   -6 .
 » 4 years ago, # | ← Rev. 2 →   +11
 » 4 years ago, # | ← Rev. 2 →   -8 It's not exactly Dijkstra but still an interesting problem: Hackerearth: Novermber Easy 16' Trustworthy network
 » 4 years ago, # |   0
 » 4 years ago, # |   +5 http://serjudging.vanb.org/wp-content/uploads/NAIPC-2014-Problems.pdf (2014 North American Invitational Programming Contest)Problem F
•  » » 3 years ago, # ^ |   0 Can I ask how can we solve the problem you mentioned?Thanks.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 First, find all the villages that when robbed, there will be no way to travel from 2->1. (This can be done by trial using BFS), and set the gold for those villages to 0.After that, the problem becomes finding the maximum weighted path in DAG.
 » 3 years ago, # |   +11
 » 15 months ago, # |   0
 » 13 months ago, # |   +5 A slight modification of Dijkstra. Not sure if the difficulty is what you're asking for.B — Planets
 » 5 months ago, # |   0 how do we solve 449b .i didn't understand the editorial