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

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

Восстановить пароль Регистрация
 
Maaksi
1 / 1 / 0
Регистрация: 20.01.2014
Сообщений: 16
03.07.2014, 16:49     В чем может быть ошибка. Расстояние между вершинами дерева #1
Входные данные:
Первая строка содержит количество вершин в дереве 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 минут
З.ы: Код не проходит несколько тестов...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.07.2014, 18:12     В чем может быть ошибка. Расстояние между вершинами дерева #2
не проходит-то по времени?

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

Не по теме:

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

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

Найти максимальное и среднее расстояние между центральными вершинами неориентированного графа C++
Найти минимальное расстояние между вершинами 1 и N графа C++
Вылетает "strcpy_s", в чем может быть ошибка? C++

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

Или воспользуйтесь поиском по форуму:
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
04.07.2014, 09:23     В чем может быть ошибка. Расстояние между вершинами дерева #10
SlavaSSU, ну не знаю - тут ТС запускал Дейкстру каждый раз и не прошло по его словам всего несколько тестов.
Yandex
Объявления
04.07.2014, 09:23     В чем может быть ошибка. Расстояние между вершинами дерева
Ответ Создать тему
Опции темы

Текущее время: 18:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru