Блог пользователя minimario

Автор minimario, история, 7 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

This problem.

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

Hackerearth: Novermber Easy 16' Trustworthy network

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

Problem F

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

B — Planets

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

this one is cool

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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