Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.53/34: Рейтинг темы: голосов - 34, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 13.11.2015
Сообщений: 5

Длина пути (поиск в ширину)

09.03.2017, 14:00. Показов 6297. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Гарантируется, что путь существует.
Входные данные
Во входном файле записаны в первой строке число N - количество вершин в графе (1<N≤100) и M – количество ребер. Затем записаны M пар целых чисел – номера вершин определяющих ребра. Затем записаны номера двух вершин - начальной и конечной.
Выходные данные
В выходной файл выведите в первой строке - длину пути (количество ребер, которые нужно пройти), а во второй путь от начальной до конечной вершины.

Пример:
input.txt
7 6
1 2
1 5
3 4
2 3
3 6
6 7
3 5

output.txt
3
3 2 1 5
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
09.03.2017, 14:00
Ответы с готовыми решениями:

Поиск пути в двумерном массиве методом "в ширину"
Все что имею: Двумерный массив, заполненный нулями(стенками) и единицами(пустотой). Положение игрока X и Y. И положение цели, X0 и Y0. ...

длина пути
За время т=100с скоростью поезда уменьшилось от v1=70 км/ч до v2=38 км/ч. Считая движение поезда равнозамедленным найти путь, пройденный...

Деревья (длина пути ...)
Используя очередь или стэк написать функцию, которая находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины Е;...

1
7 / 7 / 9
Регистрация: 20.11.2016
Сообщений: 120
09.03.2017, 20:33
Лучший ответ Сообщение было отмечено BlackPrince как решение

Решение

ни хрена не понял;
поясните на примере!


Во входном файле записаны в первой строке число N - количество вершин в графе (1<N≤100) и M – количество ребер
Значит, относительно примера
7 вершин в графе и 6 рёбер

Затем записаны M пар целых чисел – номера вершин определяющих ребра.
1 2
1 5
3 4
2 3
3 6
6 7

Затем записаны номера двух вершин - начальной и конечной.
Значит начальная вершина 3 и конечная -5

Со вторым файлом всё понятно.

Добавлено через 3 часа 10 минут
всё, сделал -ГОТОВО.


вот верный код
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <fstream>
#include <iostream>
#include <vector>
#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
/*
algorythm poiska v shirinu
 
int n;
int m;
vector<int> *adj;
vector<bool> used;
queue<int> q;
 
void bfs(int v) {
    if (used[v]) {
        return;
    }
    q.push(v);
    used[v] = true;
    while (!q.empty()) {
        v = q.front();
        q.pop();
        printf("%d ", (v + 1));
                for (int i = 0; i < adj[v].size(); ++i) {
            int w = adj[v][i];
                        if (used[w]) {
                continue;
            }
            q.push(w);
            used[w] = true;
    }
}
 
 
void readData() {
    scanf("%d %d", &n, &m);
    adj = new vector<int>[n];
 
    for (int i = 0; i < m; ++i) {
        int v, w;
        scanf("%d %d", &v, &w);
        v--;
        w--;
        adj[v].push_back(w);
    }
 
       used.resize(n, false);
}
 
void run() {
    readData();
    for (int v = 0; v < n; ++v) {
        bfs(v);
    }
      for (int i = 0; i < n; ++i) {
        adj[i].clear();
    }
    delete[] adj;
 
    used.clear();
}
*/
 
int main()
{
    setlocale(LC_ALL, "RUSSIAN");
    ifstream in("input.txt");
 
    if (in.is_open())
    {
 
        int count = 0;
        int temp;
 
        while (!in.eof())
        {
            in >> temp;
            count++;
        }
 
        in.seekg(0, ios::beg);
        in.clear();
 
        int count_space = 0;
        char symbol;
        while (!in.eof())
        {
 
            in.get(symbol);
            if (symbol == ' ') count_space++;
            if (symbol == '\n') break;
        }
 
        in.seekg(0, ios::beg);
        in.clear();
 
 
        int n = count / (count_space + 1);
        int m = count_space + 1;
        double **x;
        x = new double*[n];
        for (int i = 0; i<n; i++) x[i] = new double[m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                in >> x[i][j];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                cout << x[i][j] << "\t";
            cout << "\n";
        }
        ofstream fout("output.txt");
        for( int i = 0; i < n; i++ )
        {
           for( int j = 0; j < m; j++ )
        fout << x[i][j]<<"\t";
        fout << "\n";
        }
        fout.close();
 
        for (int i = 0; i<n; i++) delete[] x[i];
        delete[] x;
 
        in.close();
    }
    else
    {
        cout << "File not found";
    }
    return 0;
}

про алгоритм подробнее можно почитать здесь
http://cybern.ru/obxod-v-shiri... -na-c.html

Код верный. Но комментарии за отдельную плату

Добавлено через 1 минуту
делал для обработки любых чисел в файле, так и для условий задачи.

Как на входе, так и на выхлопе - в файле оутпут.
Граф хранится в двумерном массиве.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
09.03.2017, 20:33
Помогаю со студенческими работами здесь

Длина пути и кириллица
как подсчитываются символы в пути к файлу в лотусе? Например: C:\Folder\subfolder\file.doc - 28 символов и C:\Folder\первая...

Поиск пути к файлам по фрагменту этого пути
Здравствуйте. У меня есть код, который удаляет все .txt файлы из определенной папки, конкретно из папки C:\Users\Кирилл\Desktop\66\ ...

Поиск пути в играх. Алгоритм поиска пути A*
В своё время долго и упорно разбирал различные алгоритмы поиска путей для различных задач. Сейчас, во время отпуска, решил сделать доброе...

Длина тормозного пути состава
Уважаемые форумчане. Буду очень благодарен за помощь в решении следующей задачи. Маневровая лебедка (трос) тянет состав (ж.д. вагоны)...

Длина пути между городами
Прошу помощи в решении задачи. Я не могу поняты как это сделать потому прошу вашей помощи. Надо найти путь который прошел...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru