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

Найти количество всевозможных маршрутов от города до города

11.12.2015, 01:15. Показов 1646. Ответов 2
Метки нет (Все метки)

Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти количество всевозможных маршрутов с города с номером start до города с номером finish. Маршруты без циклов.
Формат входного файла
Во входном файле в первой строке записаны два числа n и m, задающие соответственно количество городов и количество дорог (1≤n≤100, 0≤m≤10000), со второй строки заданы m пар чисел - дороги. В последней строке заданы два числа - start и finish.
Формат выходного файла
В выходной файл выведите одно число – количество групп озер.

Примеры
input.txt
4 6
1 2
1 3
1 5
2 3
3 4
4 5
1 3
output.txt
3
Примечание
Имеем следующие пути:
1 2 3
1 3
5 4 3
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.12.2015, 01:15
Ответы с готовыми решениями:

Посчитать количество замкнутых маршрутов, проходящий ровно через четыре различных города
Задача E. Тетрациклофобия Имя входного файла: phobia.in Имя выходного файла: phobia.out...

Для заданной вершины p найти маршруты в другие города, хотя бы один маршрут для каждого города
Добрый день мои дорогие и многоуважаемые форумчане. Прошу вашей помощи: Вот дали задание в...

Найти маршрут перелета из города А в город В, не содержащий города С
Нужна помощь с написанием программы про пути в ориентированном графе. Текст задания: Дан список...

Найти для 1-го города кратчайшие пути в другие города
Есть некоторое количество городов, некоторые из которых соединены дорогами известной длины. Вся...

2
4455 / 2074 / 263
Регистрация: 01.03.2013
Сообщений: 5,516
Записей в блоге: 22
11.12.2015, 05:52 2
Лучший ответ Сообщение было отмечено Akatosh как решение

Решение

Цитата Сообщение от Akatosh Посмотреть сообщение
Найти количество всевозможных маршрутов
Цитата Сообщение от Akatosh Посмотреть сообщение
соединяющих дорог
Цитата Сообщение от Akatosh Посмотреть сообщение
В выходной файл выведите одно число – количество групп озер.

Цитата Сообщение от Akatosh Посмотреть сообщение
Найти количество всевозможных маршрутов с города с номером start
Цитата Сообщение от Akatosh Посмотреть сообщение
Имеем следующие пути:
...
5 4 3


Но поскольку все равно всем (включая ТС) пофиг, где там какие озера и дороги, вот кот. "Прямой, без извилин", без динамических массивов и STL (хотя нормальные контейнеры были бы кстати), велосипеды с паскалевскими массивами и т.п., но вполне идейно и работоспособно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int g[101][102], w[1000], S, F, f(int, int *);
 
bool c(int n, int *p) {return p<w ? false : *p==n || c(n, p-1);}
 
int s(int *p) {if (*p) {cout<<(p==w ? "" : "-")<<*p; s(p+1);} else {cout<<'\n'; return 1;}}
 
int l(int n, int *p, int j) {return g[n][j] ? f(g[n][j],p+1) + l(n,p,j+1) : 0;}
    
int f(int n, int *p) {*p=n; int r = c(n,p-1) ? 0 : n==F ? s(w) : l(n,p,1); *p=0; return r;}
 
void t(int i) {if (i) {int a,b; cin>>a>>b; g[a][0]++; g[a][g[a][0]]=b; t(i-1);}}
 
int main() {int n,m; cin>>n>>m; t(m); cin>>S>>F; cout<<"res = "<<f(S,w);}
ЗЫ да, в моем коте дороги односторонние. Если они двусторонние, надо просто чуть доработать процедуры заполнения графа из входного потока:
C++
1
2
void t(int i) {if (i) {
    int a,b; cin>>a>>b; g[a][0]++; g[a][g[a][0]]=b; g[b][0]++; g[b][g[b][0]]=a; t(i-1);}}
0
0 / 0 / 0
Регистрация: 24.11.2015
Сообщений: 14
29.12.2015, 19:28  [ТС] 3
(Условие было некорректное, вот корректное условие)
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти количество всевозможных маршрутов с города с номером start до города с номером finish. Маршруты без циклов.
Формат входного файла
Во входном файле в первой строке записаны два числа n и m, задающие соответственно количество городов и количество дорог (1≤n≤100, 0≤m≤10000), со второй строки заданы m пар чисел - дороги. В последней строке заданы два числа - start и finish.
Формат выходного файла
В выходной файл выведите одно число – количество возможных маршрутов.

Примеры
input.txt
4 6 (n и m)
1 2
1 3
1 5
2 3
3 4
4 5
1 3 (Это start и finish)

output.txt
3

Примечание
Имеем следующие маршруты:
1 2 3
1 3
1 5 4 3
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
29.12.2015, 19:28

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

Для 1-го города найти кратчайшие маршруты в остальные города
Имеется n городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана...

ID города в соответствии с названием города функцией из базы городов в Excel
Здравствуйте. Появился вопрос по Excel. Есть некая база городов (их свыше 1000 по России). На...

Как зайти на сайт одного города с другого города под ip-шнику первого?
Подскажите пожалуйста, что нужно сделать чтобы заходя из города А. на определенный сайт города Б....

Правда что жители города N отличаются от жителей города L?
Может быть это очевидно, но мне не очень верится. Если города разных стран, то это понятно: разный...


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

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

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