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)
- 715B - Дополни граф (precisely the type I want)
- 449B - Jzzhu и города (really easy, but still a Dijkstra with modif)
- 59E - Кратчайший путь
- 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!
This problem.
This problem was really fun! Thank you for your suggestion.
I solved the last one before, it's really amazing and unexpected!
Could you give a hint to the Sum problem..
Create a graph where the nodes are all possible remainders mod the smallest element of A.
Oh ok. thanks.
the last link isn't working, any alternatives?
sum (you will need to use translate)
567E - Президент и дороги
Kth shortest path problem. Not easy, but cool :)
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?
click
Can you provide a hint for this problem ?
Store K shortest paths to each node and do dijkstra with those.
Here I explained how you can solve it. My code is here.
There is a $$$O((n + k) \log m)$$$ algorithm. Its implementation uses a strange data structure. You can read it from here.
Here are some more:
http://mirror.codeforces.com/problemset/gymProblem/100589/K
Interesting problem IMO
.
Here are few problems:
HackerRank Week of Code 20 — Synchronous Shopping
IEEE Xtreme 10.0 — Island Hopping
UVa 10356 — Rough Roads
UVa 11367 — Full Tank
Light OJ 1099 — Not the Best
It's not exactly Dijkstra but still an interesting problem:
Hackerearth: Novermber Easy 16' Trustworthy network
IOI'11 Crocodile's Underground City
http://serjudging.vanb.org/wp-content/uploads/NAIPC-2014-Problems.pdf (2014 North American Invitational Programming Contest)
Problem F
Can I ask how can we solve the problem you mentioned?Thanks.
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.
406 Div. 1 B
https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/booze-first-76e979dd/ A really cool problem.
A slight modification of Dijkstra. Not sure if the difficulty is what you're asking for.
B — Planets
this one is cool