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

pomogite reshit zadachu
Автор Matsur, 13 лет назад, По-русски

Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин определить: существует кратчайший путь между ними или нет.

Кратчайший путь может не существовать по двум причинам: либо нет ни одного пути, либо есть путь сколь угодно маленького веса.

Входные данные

В первой строке входного файла INPUT.TXT записано единственное число N (1 <= N <= 100) - количество вершин графа. В следующих N строках по N чисел - матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j), в которой число 0 обозначает отсутствие ребра, а любое другое число - наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк по N чисел: j-ое число в i-ой строке должно быть равно 0, если путь из i в j не существует, 1 - если существует кратчайший путь, и 2 - если существует путь сколь угодно маленького веса.

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Эх, как много праздников чудесных нам приносит весна... А ведь не будь Codeforces, я бы и не узнал о них. Поздравляю)))
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
дай угадаю - копипаст с acm.dvpion.ru?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
а вот тебе почитать на досуге (olympiads.ru):
раз
два

а если уж совсем серьезно (e-maxx.ru):
раз
два
→ Ответить
13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
по-моему пора новичкам или "Не в рейтинге" запрещать создавать посты.... или пусть посты сперва проходят модерацию и потом лишь появляются в эфире.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Умник, чем тебе его пост навредил?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится

      "навредил" :)

      наверно красиво будет, если весь эфир будет засран подобными вопросами? к тому же у ЭТОЙ задачи есть на ТОМ сайте ОБСУЖДЕНИЕ, если даже не разбор.

      причем автор даже не потрудился указать ни свой код, ни на чем ему "помочь" решить (Haskell? Ruby? F#? Whitespace?) - ничего... поэтому стоит ли такому срачу иметь место?

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        такие вопросы быстро бы уходили с прямого эфира, если бы  на них адекватно отвечали или вообще игнорили, а не писали о том, как им надоели такие посты. 
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Единственное, что меня бесит, так это транслит в названии поста.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        рискну предположить, что у него русского языка нету на компе.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится
          Пусть ставит. Я из Хорватии, из Туниса и из Турции писал на русском. Причем клавы там естественно без русских символов и русской раскладки по умолчанию нет.
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А у тебя клавиш "SHIFT" и "CAPS LOCK" нет.
          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Все мы учимся. И все начинаем с малого...
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Пора сделать два прямых эфира. Может быть, один платный, за ВКшные голоса :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится
      Есть люди оранжево-красного оттенка, которым, зачастую, есть чем поделиться с обществом, но они сугубо клали на социальные сети.
      Я по-прежднему солидарен с любым мнением, которое настроено на ущемление прав людей "не в рейтинге" (лишение права создавать посты, ставить оценки), потому что они (кроме частных случаев) не являются частью общества. А этого парня я бы даже всерьез не воспринимал, самообучение это явно не для него.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это не выход. Тот-же "не в рейтинге" может сделать себе зеленый рейтинг просто сдав либо-что на одном контесте. И что? Он теперь является частью общества?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Тот же, да не тот же. В основном такие "не в рейтинге" ленятся просто сдать что-либо на одном контесте.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            Вообще это "что-либо" может служить любым файлом, ведь что-бы участвовать в распределении рейтинга достаточно получить хотя-бы "compilation error".
            → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
              Во-первых, посмотрите на этих людей "не в рейтинге", просящих решить им задачку: они ведь иной раз после формулировки условия даже не догадываются дописать "помогите решить, пожалуйста" - Вы всерьёз полагаете, что они будут ради возможности постинга отправлять хотя бы "что-либо" и что они вообще понимают, по каким принципам вычисляется рейтинг?
              Во-вторых, можно ведь поднять планку на возможность постинга до зелёного (или даже синего) цвета.
              А тех людей, которые пишут дельные вещи, но при этом принципиально не участвуют в контестах либо участвуют крайне плохо, можно по пальцам одной руки пересчитать - думаю, администрации не составит труда по их письму с запросом разрешить им постинг в порядке исключения.
              P.S. Я добавил "или даже синего" после того, как внимательно посмотрел на профиль топикстартера.
              → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Забавно видеть такие просьбы о помощи)

В чём конкретно проблема-то?

→ Ответить