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

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

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

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

01.10.2013, 02:35. Просмотров 749. Ответов 12
Метки нет (Все метки)

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

Расстояние между двумя ближайшими городами - C++
Помогите пжалста. В некотором государстве n городов. Найти расстояние между двумя ближайшими городами от города A. Входные данные В...

Расстояние между двумя множествами точек - это расстояние между наиболее близко расположенными точками этих - C++
1. Расстояние между двумя множествами точек - это расстояние между наиболее близко расположенными точками этих множеств. Найти расстояние...

Задача на рекурсию. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги - C++
Дана матрица размером NxN с расстояниями между городами при наличии прямой дороги между ними. По вертикали содержаться города откуда...

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

Найти минимальное количество пересадок между двумя городами - C++
Здраствуйте!Помогите пожалуйста Кратчайший путь. Даны N городов и связи между ними в виде матрицы смежности. Требуется найти...

Расстояние между двумя точками - C++
1. Напишите функцию distance, которая вычисляет расстояние между двумя точками (x1, y1) и (x2, y2). Все числа и возвращаемые значения...

12
Tsin
715 / 460 / 132
Регистрация: 30.12.2012
Сообщений: 1,251
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 02:43 #2
BobbyCharlton, если не хотите ничего делать сами - тогда вам в раздел Фриланс.
Если же готовы "сотрудничать" - пожалуйста) Будем думать вместе!
0
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 02:54  [ТС] #3
ну вот мне немножко помогли (AntonChik) с планом:
1.строите граф(дерево)
2.находите ближайшие к A вершины , это труда составить не должно
3.делаете
Обход дерева
Обход дерева
от одной вершины к другой в поисках минимального пути
0
Tsin
715 / 460 / 132
Регистрация: 30.12.2012
Сообщений: 1,251
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 03:01 #4
BobbyCharlton, мне более привлекательной кажется идея построить матрицу смежности.
Для начала сделайте вот что : считайте первые два параметра (N, M) из файла и создайте двумерный массив подходящего размера. Справитесь?
0
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 03:10  [ТС] #5
Tsin, мне именно с графами сделать надо.
0
Tsin
715 / 460 / 132
Регистрация: 30.12.2012
Сообщений: 1,251
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 03:18 #6
BobbyCharlton, матрица смежности не что иное, как одно из представлений графа. Так что я думаю, что тут проблемы нет. Или есть по-вашему?
0
BobbyCharlton
0 / 0 / 0
Регистрация: 15.09.2013
Сообщений: 8
01.10.2013, 03:40  [ТС] #7
Tsin, есть
0
Tsin
715 / 460 / 132
Регистрация: 30.12.2012
Сообщений: 1,251
Записей в блоге: 2
Завершенные тесты: 3
01.10.2013, 03:51 #8
BobbyCharlton, ну хорошо. Тогда начните с описания структуры данных, с которой будете работать.
0
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
01.10.2013, 05:29 #9
Цитата Сообщение от BobbyCharlton Посмотреть сообщение
Найти расстояние между двумя ближайшими городами от города A
В приведенном примере получается такая картинка:
Расстояние между двумя ближайшими городами
Первая ближайшая к 2 вершина это 3, а вот вторых ближайших уже две: 4 (через 2-4) и 1 (через 2-3-1). Т.е. решение не однозначное в такой формулировке.
0
ya_noob
_
201 / 145 / 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 ищем расстояние от В к С, иначе от С к В
0
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
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];
}
0
ya_noob
_
201 / 145 / 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 ребра
0
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
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)
Согласен, немного напутал с очередностью циклов.
0
01.10.2013, 20:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2013, 20:41
Привет! Вот еще темы с ответами:

Расстояние между двумя точками - C++
Найти расстояние между двумя точками (x1, y1) и (x2, y2) Формат входных данных Одна строка входных данных содержит четыре...

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

Расстояние между двумя прямыми(модуль) - C++
Нужно просто срочно!!! Пояснение задания лабы: Тобто, якщо Ваше завдання звучить так: &quot;Записати рівняння прямої лінії, яка...&quot;, то Ви...

Найти расстояние между двумя точками на плоскости - C++
Даны четыре действительных числа: x1, y1, x2, y2. Напишите функцию distance(x1, y1, x2, y2), вычисляющую расстояние между точкой (x1. y1) и...


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

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

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