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

A problem about weighted graphs
Автор Dalisyron, история, 9 лет назад, По-английски

Problem :

Given a weighted directed graph with both negative and positive edges, Find a path from vertex 1 to n, in which minimum subpath weight(starting from vertex 1) is maximum.

I can't think of any graph algorithm that can help me solve this problem, so any suggestions are appreciated.

N<=500

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

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

constraints?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

easi task

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

Binary search for the answer plus BFS to check if it's possible. Details: think.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I've never heard of BFS on weighted graph ... how would that be done ?

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

      I parsed "subpath" as "edge"...

      If they're paths from vertex 1, it's modified Dijkstra (you only have to ignore possible paths with length < checked answer).

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Could you please post the question link? I would like to solve it too.

Thanks in advance :)

→ Ответить