1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
|
||||||
1 | ||||||
В чем может быть ошибка. Расстояние между вершинами дерева03.07.2014, 16:49. Показов 1098. Ответов 9
Метки нет Все метки)
(
Входные данные:
Первая строка содержит количество вершин в дереве n(1<=n<=500000). Вершины имеют значения от 0 до n-1. В следующих n-1 строках содержится по 3 целых числа u,v,w, которые отвечают ребру весом w, соединяющему вершину u и v В следующей строке дано число m - количество запросов. В следующих m строках дано по два числа - номера вершин между которыми нужно найти расстояния. Выходные данные: На каждый запрос вывести ответ
З.ы: Код не проходит несколько тестов...
0
|
03.07.2014, 16:49 | |
Ответы с готовыми решениями:
9
В чем может быть ошибка в обмене данными между двумя текстовыми файлами? В чем может быть ошибка? В чём может быть ошибка? |
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
03.07.2014, 18:12 | 2 |
не проходит-то по времени?
Добавлено через 2 минуты делается это не Дейкстрой. Не по теме: матрица смежности на
0
|
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
|
|
03.07.2014, 18:59 [ТС] | 4 |
Ошибка выполнения, но только в некоторых вариантах.
n*n вроди бы=)
З.ы: ПОчитаю о Поиске в ширину, но только ж Дейкстрой поидеи тоже должно работать)
0
|
03.07.2014, 19:04 | 5 |
Maaksi, Дейкстрой будет работать, только долго за O(n^2) или O(n*log(n)) с кучей. Используя поиск в ширину можно добиться сложности O(V+E), где V - количество вершин в дереве, E - количество ребер.
А матрица 10^5 * 10^5 будет состоять из 10^10 чисел типа int. Посмотрим, сколько это занимает: 10^10 * 4 = 4*10^10 байт = 39 062 500 КБайт = 38 147 МБайт = 37 ГБайт. Не уверен, что у вас настолько мощный компьютер ![]()
1
|
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
|
|
03.07.2014, 19:28 [ТС] | 6 |
Пасиб) А примерно когда, если по программе то должны учить поиск в ширину и тд?)
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
04.07.2014, 00:09 | 7 |
там 500000 вершин и еще много запросов, тут и поиск в ширину на запрос не пройдет!
или что вы имеете в виду, когда говорите поиск в ширину? каждый раз его запускать?
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
04.07.2014, 02:25 | 9 |
Dani, вот именно, что неизвестно! Я уже видел такую задачу, там было чет типа 100000 вершин и столько же запросов. Ну так на первый взгляд кажется, что задача для того, чтобы решить ее, не запуская каждый раз поиск в ширину.
0
|
04.07.2014, 09:23 | 10 |
SlavaSSU, ну не знаю - тут ТС запускал Дейкстру каждый раз и не прошло по его словам всего несколько тестов.
0
|
04.07.2014, 09:23 | |
Помогаю со студенческими работами здесь
10
В чем может быть ошибка В чём может быть ошибка? В чем может быть ошибка В чем может быть ошибка? В чем может быть ошибка? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
![]() |
Новые блоги и статьи
![]() |
||||
Что нового в C# 14
UnmanagedCoder 10.03.2025
Предстоящая версия C# 14 обещает принести изменения, которые сделают разработку еще более приятной и эффективной.
Что стоит отметить, так это влияние сообщества разработчиков на формирование новых. . .
|
Формулы поворота
Igor3D 10.03.2025
Добрый день
Тема
Эти формулы приводятся во множестве тьюториалов, часто под видом "матрица вращения на плоскости".
x' = x * cos(a) - y * sin(a)
y' = y * cos(a) + x * sin(a)
Как бы Вы их. . .
|
Что нового в .NET 10
UnmanagedCoder 10.03.2025
. NET 10 выходит как релиз с длительной поддержкой (LTS), включающей три года обновлений. В этом обновлении Microsoft сфокусировались на нескольких направлениях: производительность, оптимизация. . .
|
Отложенное высвобождение, RCU и Hazard Pointer в C++26
NullReferenced 09.03.2025
Многопоточное программирование стало важной частью современной разработки. Когда несколько потоков одновременно работают с общими данными, возникает целый ряд проблем, связанных с синхронизацией и. . .
|
Неблокирующийся стек на C++26
NullReferenced 09.03.2025
Традиционные способы синхронизации в многопоточном программировании — мьютексы, семафоры, условные переменные — часто превращаются в узкое место в плане производительности. При этом неблокирующиеся. . .
|
Обработка строк в C++26: Новые возможности string и string_view
NullReferenced 09.03.2025
Новый стандарт C++26 предлагает много улучшений для работы с привычными string и относительно новыми string_view.
string_view - это невладеющая ссылка на последовательность символов, появившаяся в. . .
|
Мой первый аддон для Blender 3D, с помощью нейронки (не зная даже азов пайтона, но это не значит что так и с остальным).
Hrethgir 09.03.2025
Потратил весь день. Пол-дня мне хватило, чтобы понять что с версией с 14B мне не одолеть написание функционального кода, на языке с которым я вообще никак не знаком - пайтон. Версия 22B от другого. . .
|
Einstein@Home сегодня исполняется двадцать лет!
Programma_Boinc 09.03.2025
Einstein@Home сегодня исполняется двадцать лет!
Отправлено 19 февраля 2025 года в 17:20:21 UTC
Я хочу поздравить всех наших волонтеров, разработчиков и ученых из Einstein@Home.
Мы официально. . .
|
Заполнители и расширенный набор символов в C++26
NullReferenced 09.03.2025
C++26 представляет два важных обновления: заполнители и расширенный набор символов. Заполнители (placeholders) решают давнюю проблему лаконичности кода в шаблонных выражениях и лямбда-функциях. Они. . .
|
Контракты в C++26
NullReferenced 09.03.2025
Контракты – это механизм, позволяющий указывать предусловия, постусловия и инварианты для функций в коде. Эта функциональность должна была стать частью C++20, но была исключена на встрече комитета. . .
|