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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не получается скомпилировать и использовать файл .lib http://www.cyberforum.ru/cpp-beginners/thread966164.html
Хаюшки, мечтал сделать свою мини-библиотечку и за одно научиться работать с lib файлами, но нормального руководства нет, все либо дотошно пытаются объяснить как сделать ее в Wizard'е вижлы, либо как...
C++ Сравнить два поля узла Имеется двусвязный список фишек домино. В нём два поля: левое и правое числа фишки домино. Нужно пробежать такой цикл, чтобы выяснить соответствует ли правилам игры цепочка: т.е. равно ли правое... http://www.cyberforum.ru/cpp-beginners/thread966158.html
Удаление строк (символов) из файла C++
Подскажите, пожалуйста как реализовать программно (1) исключение из исходного текстового файла подстрок, являющихся цепочками заданного языка. И (2) оставляет в исходном текстовом файле только...
C++ не получается, хоть убеи :С
___________________________ Stellaj.txt : ___________________________ StellajZ abc_sklad Velosiped 3.4 2 polka7 KUB
C++ Ошибка при работе с объектами http://www.cyberforum.ru/cpp-beginners/thread966104.html
Доброго времени суток! Я написал программу для работы с матрицами. При умножении происходит следующее: Matrix M3 = M1 * M2; // после этого M3 = M1. Отладка показала, что возвращаемый из оператора...
C++ Нахождения цикла в орграфе Задан орграф списком смежности, при этом его вершинами являются строчные латинские символы. Описание выглядит примерно так: <описание i-ой вершины> ::= <символ, записанный в i-й вершине> <число di... подробнее

Показать сообщение отдельно
kamre
126 / 130 / 4
Регистрация: 25.12.2011
Сообщений: 443
01.10.2013, 19:58
Цитата Сообщение от 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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.