Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
1

В чем может быть ошибка. Расстояние между вершинами дерева

03.07.2014, 16:49. Показов 1098. Ответов 9
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Входные данные:
Первая строка содержит количество вершин в дереве n(1<=n<=500000). Вершины имеют значения от 0 до n-1.
В следующих n-1 строках содержится по 3 целых числа u,v,w, которые отвечают ребру весом w, соединяющему вершину u и v
В следующей строке дано число m - количество запросов. В следующих m строках дано по два числа - номера вершин между которыми нужно найти расстояния.

Выходные данные:
На каждый запрос вывести ответ

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
std::vector<int>  Dei(const  int& n,const std::vector<int>& mat,const int& Number )
{
    std::vector<bool> tr(n, false);
    std::vector<int> distance(n, INT_MAX);
    distance[Number] = mat[Number*n + Number];
    for (int i = 0; i < n; i++)
    {
        int min = INT_MAX;
        int count = 0;
        for (int j = 0; j < n; j++)
        {
            if (distance[j] <= min&&!tr[j])
            {
                count = j;
                min = distance[j];
            }
        }
        tr[count] = true;
        for (int j = 0; j < n; j++)
        {
            if (!tr[j] && mat[count*n + j] >= 0 && mat[count*n + j] + distance[count] < distance[j])
                distance[j] = mat[count*n + j] + distance[count];
        }
    }
    return distance;
}
void main()
{
    int n;//кількість вершин
    std::cin >> n;
    std::vector<int> mat(n*n, -1);
    for (int i = 0; i < n; i++)
        mat[i*n + i] = 0;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v, w;
        std::cin >> u >> v >> w;
        mat[u*n + v] = w;
        mat[v*n + u] = w;
    }
    int y;
    std::cin >> y;
    std::vector<int> vec;
    for (int i = 0; i < y; i++)
    {
        int Nu, nu2;
        std::cin >> Nu >> nu2;
        vec = Dei(n, mat, Nu);
        std::cout << vec[nu2] << std::endl;
    }
}
Добавлено через 5 минут
З.ы: Код не проходит несколько тестов...
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
03.07.2014, 16:49
Ответы с готовыми решениями:

В чем может быть ошибка в обмене данными между двумя текстовыми файлами?
// labbb4.cpp: определяет точку входа для консольного приложения. // #include &quot;stdafx.h&quot; Общая задача: сделать обмен данными между...

В чем может быть ошибка?
Вот программа: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;stdlib.h&gt; #include...

В чём может быть ошибка?
Пишет, что нету точки с запятой. Где??? #include &lt;iostream&gt; #include &lt;string&gt; using namespace std; { class Program ...

9
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
03.07.2014, 18:12 2
не проходит-то по времени?

Добавлено через 2 минуты
делается это не Дейкстрой.

Не по теме:

матрица смежности на https://www.cyberforum.ru/cgi-bin/latex.cgi?5*10^5 вершин?

0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
03.07.2014, 18:28 3
Нужно писать поиск в ширину и списки смежности.
0
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
03.07.2014, 18:59  [ТС] 4
Цитата Сообщение от salam Посмотреть сообщение
не проходит-то по времени?
Ошибка выполнения, но только в некоторых вариантах.
Цитата Сообщение от salam Посмотреть сообщение
Не по теме:
матрица смежности на вершин?
n*n вроди бы=)
З.ы: ПОчитаю о Поиске в ширину, но только ж Дейкстрой поидеи тоже должно работать)
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
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
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.07.2014, 00:39 8
SlavaSSU, количество запрсов не известно.
0
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
04.07.2014, 02:25 9
Dani, вот именно, что неизвестно! Я уже видел такую задачу, там было чет типа 100000 вершин и столько же запросов. Ну так на первый взгляд кажется, что задача для того, чтобы решить ее, не запуская каждый раз поиск в ширину.
0
1405 / 647 / 135
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
04.07.2014, 09:23 10
SlavaSSU, ну не знаю - тут ТС запускал Дейкстру каждый раз и не прошло по его словам всего несколько тестов.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
04.07.2014, 09:23
Помогаю со студенческими работами здесь

В чем может быть ошибка
Цель работы состоит в том чтобы создать электронный альбом. Не удается исправить ошибку, проблема в картинке. В чем может быть ошибка. ...

В чём может быть ошибка?
У меня программа, которая должна удалять из введенного сообщения все гласные. Использую класс - StringBuilder. - выдаёт ошибку:...

В чем может быть ошибка
В чем может быть ошибка

В чем может быть ошибка?
Есть такой небольшой скрипт: в файле links.txt хранятся ссылки на страницы сайтов. Скрипт ходит по этим страницам, парсит ссылки на...

В чем может быть ошибка?
Что означает такая ошибка? Появляться только при вводе функций explicit, ALL. Если вводить каждый элемент по отдельности, то...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
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, но была исключена на встрече комитета. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru