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

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

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

Студворк — интернет-сервис помощи студентам
Входные данные:
Первая строка содержит количество вершин в дереве 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 минуты
делается это не Дейкстрой.

Не по теме:

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

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru