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

Расстояние между двумя ближайшими городами - C++

Восстановить пароль Регистрация
 
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 02:35     Расстояние между двумя ближайшими городами #1
Помогите пжалста. Как бы тупо это не звучало, пжалста сделайте эту задачу для меня
В некотором государстве n городов. Найти расстояние между двумя ближайшими городами от города A.
Входные данные
В первой строке входного файла три числа: N, M, A (3≤N≤100), где N - количество вершин графа, M – количество ребер, A - начальная вершина. В следующих M строках заданы по 3 числа, номера вершин и расстояние между ними.
Выходные данные
Расстояние между двумя ближайшими городами от города A. Гарантируется, что решение единственно.
Пример
Input.txt
4 4 2
1 2 6
1 3 2
2 3 3
2 4 5
Output.txt
8
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.10.2013, 02:35     Расстояние между двумя ближайшими городами
Посмотрите здесь:

Вычислить расстояние между двумя точками на плоскости C++
C++ Расстояние между двумя точками
C++ Найти минимальное количество пересадок между двумя городами
C++ Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги
Расстояние между двумя ближайшими городами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tsin
 Аватар для Tsin
419 / 395 / 108
Регистрация: 30.12.2012
Сообщений: 1,085
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 02:43     Расстояние между двумя ближайшими городами #2
BobbyCharlton, если не хотите ничего делать сами - тогда вам в раздел Фриланс.
Если же готовы "сотрудничать" - пожалуйста) Будем думать вместе!
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 02:54  [ТС]     Расстояние между двумя ближайшими городами #3
ну вот мне немножко помогли (AntonChik) с планом:
1.строите граф(дерево)
2.находите ближайшие к A вершины , это труда составить не должно
3.делаете
Обход дерева
Обход дерева
от одной вершины к другой в поисках минимального пути
Tsin
 Аватар для Tsin
419 / 395 / 108
Регистрация: 30.12.2012
Сообщений: 1,085
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 03:01     Расстояние между двумя ближайшими городами #4
BobbyCharlton, мне более привлекательной кажется идея построить матрицу смежности.
Для начала сделайте вот что : считайте первые два параметра (N, M) из файла и создайте двумерный массив подходящего размера. Справитесь?
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 03:10  [ТС]     Расстояние между двумя ближайшими городами #5
Tsin, мне именно с графами сделать надо.
Tsin
 Аватар для Tsin
419 / 395 / 108
Регистрация: 30.12.2012
Сообщений: 1,085
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 03:18     Расстояние между двумя ближайшими городами #6
BobbyCharlton, матрица смежности не что иное, как одно из представлений графа. Так что я думаю, что тут проблемы нет. Или есть по-вашему?
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 03:40  [ТС]     Расстояние между двумя ближайшими городами #7
Tsin, есть
Tsin
 Аватар для Tsin
419 / 395 / 108
Регистрация: 30.12.2012
Сообщений: 1,085
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 03:51     Расстояние между двумя ближайшими городами #8
BobbyCharlton, ну хорошо. Тогда начните с описания структуры данных, с которой будете работать.
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
01.10.2013, 05:29     Расстояние между двумя ближайшими городами #9
Цитата Сообщение от BobbyCharlton Посмотреть сообщение
Найти расстояние между двумя ближайшими городами от города A
В приведенном примере получается такая картинка:
Расстояние между двумя ближайшими городами
Первая ближайшая к 2 вершина это 3, а вот вторых ближайших уже две: 4 (через 2-4) и 1 (через 2-3-1). Т.е. решение не однозначное в такой формулировке.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.10.2013, 19:44     Расстояние между двумя ближайшими городами #10
Цитата Сообщение от kamre Посмотреть сообщение
Первая ближайшая к 2 вершина это 3, а вот вторых ближайших уже две: 4 (через 2-4) и 1 (через 2-3-1). Т.е. решение не однозначное в такой формулировке.
Цитата Сообщение от BobbyCharlton Посмотреть сообщение
Гарантируется, что решение единственно.
моя версия решения:
1. строим граф (лучше на матрице смежности, т.к. вершин мало)
2. применяем дейкстру для вершины А.
3. на основе результатов пункта 2) ищем 2 кратчайших расстояния от А (т.е. 2 ближайших города В и С)
4. применяем дейкстру для любого из городов В или С
5. если на предыдущем шаге был выбран город В, то на основе результатов пункта 4 ищем расстояние от В к С, иначе от С к В
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
01.10.2013, 19:58     Расстояние между двумя ближайшими городами #11
Цитата Сообщение от ya_noob Посмотреть сообщение
моя версия решения:
1. строим граф (лучше на матрице смежности, т.к. вершин мало)
2. применяем дейкстру для вершины А.
3. на основе результатов пункта 2) ищем 2 кратчайших расстояния от А (т.е. 2 ближайших города В и С)
4. применяем дейкстру для любого из городов В или С
5. если на предыдущем шаге был выбран город В, то на основе результатов пункта 4 ищем расстояние от В к С, иначе от С к В
Так в его же примере входных данных единственность пары (B, C) не гарантирована. А вообще зачем здесь дейкстра? Можно по простому:
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
#include <fstream>
#include <vector>
#include <limits>
 
using namespace std;
 
int main() {
    ifstream inp("Input.txt");
    int n, m, a;
    inp >> n >> m >> a;
    const int inf = numeric_limits<int>::max();
    typedef vector<int> row;
    vector<row> d(n, row(n, inf));
    for (int i = 0; i < n; ++i) {
        d[i][i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int from, to, dist;
        inp >> from >> to >> dist;
        d[from - 1][to - 1] = dist;
        d[to - 1][from - 1] = dist;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (d[i][k] != inf && d[k][j] != inf)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int nearest = -1, nearest_dist = inf;
    int nearest_2nd = -1, nearest_2nd_dist = inf;
    for (int i = 0; i < n; ++i) {
        if (a - 1 == i)
            continue;
        int dist = d[a - 1][i];
        if (nearest_dist > dist) {
            nearest_2nd = nearest;
            nearest_2nd_dist = nearest_dist;
            nearest = i;
            nearest_dist = dist;
        } else if (nearest_2nd_dist > dist) {
            nearest_2nd = i;
            nearest_2nd_dist = dist;
        }
    }
    ofstream out("Output.txt");
    out << d[nearest][nearest_2nd];
}
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.10.2013, 20:31     Расстояние между двумя ближайшими городами #12
Цитата Сообщение от kamre Посмотреть сообщение
А вообще зачем здесь дейкстра
дейкстра: сложность O(N^2), два дейкстры 2*O(N^2) (грубо говоря 20 тыс. операций)
ваше же решение (строки 23-30): во-первых O(N^3) (также загрубляя миллион операций), а во-вторых (я так понимаю вы хотели применить флойда), неверен, т.к. вершина по которой происходит релаксация должна быть во внешнем цикле, а у вас она во внутреннем (k). ваш алгоритм гарантирует нахождение только путей длины 2 ребра
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2013, 20:41     Расстояние между двумя ближайшими городами
Еще ссылки по теме:

Расстояние между двумя локальными минимумами C++
C++ Расстояние между двумя точками через классы
C++ Расстояние между двумя точками

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

Или воспользуйтесь поиском по форуму:
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 438
01.10.2013, 20:41     Расстояние между двумя ближайшими городами #13
Цитата Сообщение от ya_noob Посмотреть сообщение
дейкстра: сложность O(N^2), два дейкстры 2*O(N^2) (грубо говоря 20 тыс. операций)
ваше же решение (строки 23-30): во-первых O(N^3)
А какая разница для
(3≤N≤100)
?
Цитата Сообщение от ya_noob Посмотреть сообщение
во-вторых (я так понимаю вы хотели применить флойда), неверен, т.к. вершина по которой происходит релаксация должна быть во внешнем цикле, а у вас она во внутреннем (k)
Согласен, немного напутал с очередностью циклов.
Yandex
Объявления
01.10.2013, 20:41     Расстояние между двумя ближайшими городами
Ответ Создать тему
Опции темы

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