minimario's blog

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This problem.

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

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

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

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

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

  • »
    »
    6 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.

    • »
      »
      »
      6 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.

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

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

this one is cool

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please tell me how can I implement this problem solution? https://codeforces.com/contest/59/problem/E