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

Задача про три города
Автор Aventador, 10 лет назад, По-русски

Помогите, пожалуйста, решить задачу. Есть n городов и m дорог. Нужно найти минимальный путь из города А в город В так, чтобы путь лежал через город С и не проходил более одного раза через любой город. N<=30000, M<=50000.

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

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

как и ожидал, сказал фигню

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

А путь обязательно простой?

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

    Упс. Надо учиться читать условия целиком.

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

    Если бы можна было проходить через любой город более одного раза, эта задача решалася бы в две дейкстры

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

      Да даже в одну, пожалуй. Из вершины С.

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

      кажется в итоге она и решилась двумя дийкстрами :) дважды надо пульнуть поток из С.

      → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

Можно раздвоить каждую вершину на 2, всем ребрам сделать пропускную способность 1 и найти минимальный по стоимости поток из вершины C в вершины A и B размера 2. Вроде что-то подобное должно решить.

→ Ответить