minimario's blog

By minimario, history, 3 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

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This problem.

»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved the last one before, it's really amazing and unexpected!

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you give a hint to the Sum problem..

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Create a graph where the nodes are all possible remainders mod the smallest element of A.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    3 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?

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it
»
3 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

»
3 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

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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.

»
22 months ago, # |
  Vote: I like it +11 Vote: I do not like it