ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1450. Российские газопроводы

Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Послано Luka Bulatovic 21 авг 2011 03:13
I did Dijkstra algorithm for S to F, but seems to exceeds time on test #3 ? Anyone got a clue? Tnx in advance
Re: Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Послано Leonid (SLenik) Andrievskiy 16 сен 2011 04:58
Well, I do not know what this test is, but the answer for this test is "No solution".
Re: Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Послано Smilodon_am [Obninsk INPE] 8 дек 2018 02:11
I don't know how to solve this problem with Dijkstra algorithm.

My approach is another.

Perhaps one pair of tests below can help you to understand the problem more clearely:

7 7
1 2 10
2 3 10
3 4 5
1 5 1
5 6 50
6 7 50
7 3 50
1 4
ans:
156

7 7
1 2 10
2 3 10
3 4 5
1 5 50
5 6 50
6 7 50
7 3 50
1 4
ans:
205
Re: Wtf is wrong with Test #3 ?!?!?!??! Dijkstra not working here???
Послано Markfryazino 29 янв 2019 17:38
What you need to do is to find the path with maximum weights of all edges while Dijkstra tries to find minimum. You're solving the wrong problem.