Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 02.05.2013
Сообщений: 10
1

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

02.05.2013, 02:30. Просмотров 1171. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.05.2013, 02:30
Ответы с готовыми решениями:

Определить количество перелетов туда и обратно между двумя городами
Не могу понять, как сделать это чудо: A. Между офисами ограничение по времени на тест2 секунды...

Расстояние между двумя ближайшими городами
Помогите пжалста. Как бы тупо это не звучало, пжалста сделайте эту задачу для меня:wall: В...

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

Найти минимальное расстояние между городами
Здравствуйте! Необходимо найти минимальное расстояние между городами. На вход подается список...

6
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 799
02.05.2013, 05:37 2
конкретный вопрос...
если его нет, идите читайте книжки...
0
0 / 0 / 0
Регистрация: 02.05.2013
Сообщений: 10
30.05.2013, 02:35  [ТС] 3
C++ алгоритмы на графах
найти минимальное количество пересадок
0
0 / 0 / 0
Регистрация: 02.05.2013
Сообщений: 10
06.06.2013, 03:06  [ТС] 4
Цитата Сообщение от salam Посмотреть сообщение
конкретный вопрос...
если его нет, идите читайте книжки...
C++ алгоритмы на графах
найти минимальное количество пересадок

хэлп миии

Добавлено через 8 минут
0
Форумчанин
Эксперт CЭксперт С++
8159 / 5007 / 1436
Регистрация: 29.11.2010
Сообщений: 13,458
06.06.2013, 03:29 5
Происк в ширину вам в помощь, тут все решается через него.
0
0 / 0 / 0
Регистрация: 01.10.2018
Сообщений: 30
25.04.2019, 19:38 6
#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
267 / 197 / 162
Регистрация: 02.05.2017
Сообщений: 792
25.04.2019, 20:35 7
Миша Иван, че же ты себе-то тоже bfs не напишешь?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.04.2019, 20:35

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Найти минимальное количество значений между двумя отрицательными
Привет.Если вкратце,то нужно найти минимальное количество значений между двумя отрицательными.Дан...

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

Найти минимальное расстояние между двумя точками
Даны два массива вещественных чисел, x и y. Их длина одинакова и равна n. Каждый (i-й) элемент...

Определить кратчайший путь между двумя городами и длину пути
задана сеть дорог в виде графа, определить кратчайший путь между двумя городами и длину пути.


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

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

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