Найти минимальное количество пересадок между двумя городами

@Nariyka · Регистрация: 02.05.2013

Студворк — интернет-сервис помощи студентам

Здраствуйте!Помогите пожалуйста
Кратчайший путь.
Даны N городов и связи между ними в виде матрицы смежности. Требуется найти минимальное количество пересадок между двумя городами. Гарантируется, что путь существует.
Входные данные
Во входном файле записано сначала число N - количество городов (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие связи, 1 - наличие связи). Затем записаны номера городов - начальной и конечной.
Выходные данные
В выходной файл выведите одно число - количество пересадок.
Пример
input.txt output.txt
5 3
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5

@salam · 02.05.2013, 05:37

конкретный вопрос...
если его нет, идите читайте книжки...

@Nariyka · 30.05.2013, 02:35 **[ТС]**

C++ алгоритмы на графах
найти минимальное количество пересадок

@Nariyka · 06.06.2013, 03:06 **[ТС]**

Сообщение от salam

конкретный вопрос...
если его нет, идите читайте книжки...

C++ алгоритмы на графах
найти минимальное количество пересадок

хэлп миии

Добавлено через 8 минут

MrGluck · 06.06.2013, 03:29

Происк в ширину вам в помощь, тут все решается через него.

@Миша Иван · 25.04.2019, 19:38

#include <fstream>
#include <string.h>
using namespace std;
int queue[100], way[100], s, visit[100], n, m, k, a[100][100];
int ans = 0, start, finish;

ifstream fin("input.txt");
ofstream fout("output.txt");

void score(int v)
{
if (v > 0)
{
score(way[v]);
s++;
}

}
void Print(int v)
{
if (v > 0)
{
Print(way[v]);
fout << v << ' ';
}
}

void bfs(int st)
{
int i = 1, j, k = 1, u;
queue[k] = st;
visit[st] = 1;
do
{
u = queue[i];
for (j = 1; j <= n; j++)
if (a[u][j] > 0 && visit[j] == 0)
{
visit[j] = 1;
way[j] = u;
queue[++k] = j;
}
i++;
} while (i <= k);
}

void Init()
{
int i, j, k;
fin >> n;
memset(way, 0, sizeof(way));
memset(a, 0, sizeof(a));
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
fin >> a[i][j];
fin >> start >> finish;
}

void main()
{
Init();
bfs(start);
score(finish);
fout << (s - 1) << "\n";
}

@LegionK · 25.04.2019, 20:35

Миша Иван, че же ты себе-то тоже bfs не напишешь?

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Nariyka 0 / 0 / 0 Регистрация: 02.05.2013 Сообщений: 10

	Найти минимальное количество пересадок между двумя городами 02.05.2013, 02:30. Показов 2172. Ответов 6 Метки нет (Все метки) Здраствуйте!Помогите пожалуйста Кратчайший путь. Даны N городов и связи между ними в виде матрицы смежности. Требуется найти минимальное количество пересадок между двумя городами. Гарантируется, что путь существует. Входные данные Во входном файле записано сначала число N - количество городов (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие связи, 1 - наличие связи). Затем записаны номера городов - начальной и конечной. Выходные данные В выходной файл выведите одно число - количество пересадок. Пример input.txt output.txt 5 3 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	02.05.2013, 05:37
	конкретный вопрос... если его нет, идите читайте книжки... 0

@Nariyka 0 / 0 / 0 Регистрация: 02.05.2013 Сообщений: 10
	30.05.2013, 02:35 [ТС]
	C++ алгоритмы на графах найти минимальное количество пересадок 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	06.06.2013, 03:29
	Происк в ширину вам в помощь, тут все решается через него. 0

@Миша Иван 0 / 0 / 0 Регистрация: 01.10.2018 Сообщений: 30
	25.04.2019, 19:38
	#include <fstream> #include <string.h> using namespace std; int queue[100], way[100], s, visit[100], n, m, k, a[100][100]; int ans = 0, start, finish; ifstream fin("input.txt"); ofstream fout("output.txt"); void score(int v) { if (v > 0) { score(way[v]); s++; } } void Print(int v) { if (v > 0) { Print(way[v]); fout << v << ' '; } } void bfs(int st) { int i = 1, j, k = 1, u; queue[k] = st; visit[st] = 1; do { u = queue[i]; for (j = 1; j <= n; j++) if (a[u][j] > 0 && visit[j] == 0) { visit[j] = 1; way[j] = u; queue[++k] = j; } i++; } while (i <= k); } void Init() { int i, j, k; fin >> n; memset(way, 0, sizeof(way)); memset(a, 0, sizeof(a)); for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) fin >> a[i][j]; fin >> start >> finish; } void main() { Init(); bfs(start); score(finish); fout << (s - 1) << "\n"; } 0

@LegionK 393 / 263 / 193 Регистрация: 02.05.2017 Сообщений: 1,003
	25.04.2019, 20:35
	Миша Иван, че же ты себе-то тоже bfs не напишешь? 0