minimario's blog

Problems that are Dijkstra with a Twist
By minimario, history, 8 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 - Дополни граф (precisely the type I want)
  2. 449B - Jzzhu и города (really easy, but still a Dijkstra with modif)
  3. 59E - Кратчайший путь
  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?
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This problem.

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

567E - Президент и дороги

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

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

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

    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?

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

Here are some more:

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

http://mirror.codeforces.com/problemset/gymProblem/100589/K

Interesting problem IMO

→ Reply
»
8 years ago, # |
← 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
»
8 years ago, # |
← 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
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

IOI'11 Crocodile's Underground City

→ Reply
»
8 years ago, # |
  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
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← 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
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

406 Div. 1 B

→ Reply
»
5 years ago, # |
  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
»
5 years ago, # |
  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
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

this one is cool

→ Reply