Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Maaksi
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
#1

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

03.07.2014, 16:49. Просмотров 391. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2014, 16:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос В чем может быть ошибка. Расстояние между вершинами дерева (C++):

В чем может быть ошибка? - C++
Вот программа: #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...

В чем может быть ошибка, и как её вылечить? - C++
Проблема такая. Покуда я студент, то пичкают нас всяческой дрянью, и вот настал язык Си. С С++ я знаком, и ноутбук с никсами прекрасно...

В чем может быть ошибка? (передача аргументов функции) - C++
Есть двумерный массив, симулирующий игровое поле (0 означают пустоту, 8 игрок) Есть некая функция, которую я хочу использовать просто для...

В чем может быть ошибка? (пример с побитовым сдвигом) - C++
Всем доброго дня) В одной из книжек по С++ (Horton) наткнулся на такую вот небольшую задачку: unsigned s = 555; int i = (s &gt;&gt;...

Программа не работает, но ошибок не выдает. В чем может быть ошибка? - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;cstdlib&gt; #define m 8 using namespace std; int main() { int...

Программа не работает на русском языке. В чем может быть ошибка? - C++
#include&lt;iostream&gt; #include &lt;string&gt; using namespace std; int main() { setlocale (LC_ALL, &quot;rus&quot;); for (int countinue = 0;...

9
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
03.07.2014, 18:12 #2
не проходит-то по времени?

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

Не по теме:

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

0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
03.07.2014, 18:28 #3
Нужно писать поиск в ширину и списки смежности.
0
Maaksi
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
03.07.2014, 18:59  [ТС] #4
Цитата Сообщение от salam Посмотреть сообщение
не проходит-то по времени?
Ошибка выполнения, но только в некоторых вариантах.
Цитата Сообщение от salam Посмотреть сообщение
Не по теме:
матрица смежности на вершин?
n*n вроди бы=)
З.ы: ПОчитаю о Поиске в ширину, но только ж Дейкстрой поидеи тоже должно работать)
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
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
Maaksi
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
03.07.2014, 19:28  [ТС] #6
Пасиб) А примерно когда, если по программе то должны учить поиск в ширину и тд?)
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
04.07.2014, 00:09 #7
там 500000 вершин и еще много запросов, тут и поиск в ширину на запрос не пройдет!
или что вы имеете в виду, когда говорите поиск в ширину? каждый раз его запускать?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 00:39 #8
SlavaSSU, количество запрсов не известно.
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
04.07.2014, 02:25 #9
Dani, вот именно, что неизвестно! Я уже видел такую задачу, там было чет типа 100000 вершин и столько же запросов. Ну так на первый взгляд кажется, что задача для того, чтобы решить ее, не запуская каждый раз поиск в ширину.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 09:23 #10
SlavaSSU, ну не знаю - тут ТС запускал Дейкстру каждый раз и не прошло по его словам всего несколько тестов.
0
04.07.2014, 09:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2014, 09:23
Привет! Вот еще темы с ответами:

задание из книги стивен прата 6 издание глючит. в чем может быть ошибка - C++
собрал задачу, ставлю текстовый файл внутри программы, с цифровыми данными, а он не работает. файл сам рабочий, так как другая программа...

Найти минимальное расстояние между вершинами 1 и N графа - C++
Dev-C++ не компилирует программу Решил написать алгоритм 0,1-BFS void BFS(int** MasList, int** MasListW, int&amp; N,int&amp; S){ int*...

Определить, сколько может быть построено квадратов с вершинами в заданых точках - C++
Доброго времени суток! Условие: Пользователь вводит кол-во точек, затем их целочисленные координаты х и у. Нужно определить сколько...

Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа - C++
Здравствуйте. нужно найти максимальное и среднее расстояние между центральными вершинами неориентированного графа. Структура данных-список...


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

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru