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

Java. Ошибка в алгоритме или в чем-то другом?
Автор Yury_Bandarchuk, 11 лет назад, По-русски

Всем доброго времени суток! Я недавно начал изучать Java. Хочу затем использовать её на контестах, а для начала нужно набить руку:) Так вот начал я с тренировки http://mirror.codeforces.com/gym/100230 (задача B). Написал Дейкстру с кучей, ввод через BufferedReader, но все равно я получил ТЛЕ на 11-ом тесте((( Вот код: http://pastebin.com/R6zGCpPm Помогите чайнику в джаве) Заранее спасибо!

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

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

Ошибки:

1) Строки 125-130:

        if (v * 2 <= heapSize)
            if (heap[v * 2] < heap[p])
                p = v * 2;
        if (v * 2 + 1 <= heapSize)
            if (heap[v * 2 + 1] < heap[p])
                p = v * 2;

Во втором случае должно быть видимо p = v * 2 + 1.

2) Необходимо везде использовать long, потому что ответ может быть порядка 7·109. А сейчас в heap'e используется int.

3) При отсутствии ответа ничего не выводится.

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

Ну и раз уж вы пишете на новом языке, хорошей идеей было бы разобраться, что есть в стандартной библиотеке. Например, можно использовать PriorityQueue или TreeSet для реализации дейкстры.

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

    Про TreeSet: писать с ним Дейкстру категорически не рекомендую. Работает слишком медленно.

    → Ответить