minimario's blog

Problems that are Dijkstra with a Twist
By minimario, history, 10 years ago, In English

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!

  • Vote: I like it
  • +48
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

This problem.

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it
→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

567E - President and Roads

→ Reply
»
10 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

Kth shortest path problem. Not easy, but cool :)

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

Here are some more:

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

http://codeforces.me/problemset/gymProblem/100589/K

Interesting problem IMO

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it +11 Vote: I do not like it

Here are few problems:

  1. HackerRank Week of Code 20 — Synchronous Shopping

  2. IEEE Xtreme 10.0 — Island Hopping

  3. UVa 10356 — Rough Roads

  4. UVa 11367 — Full Tank

  5. Light OJ 1099 — Not the Best

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it -8 Vote: I do not like it

It's not exactly Dijkstra but still an interesting problem:

Hackerearth: Novermber Easy 16' Trustworthy network

→ Reply
»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

IOI'11 Crocodile's Underground City

→ Reply
»
10 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

http://serjudging.vanb.org/wp-content/uploads/NAIPC-2014-Problems.pdf (2014 North American Invitational Programming Contest)

Problem F

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can I ask how can we solve the problem you mentioned?Thanks.

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

406 Div. 1 B

→ Reply
»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/practice-problems/algorithm/booze-first-76e979dd/ A really cool problem.

→ Reply
»
7 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

A slight modification of Dijkstra. Not sure if the difficulty is what you're asking for.

B — Planets

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

this one is cool

→ Reply