Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.12.2012, 18:13   #1
Lodyr
Пользователь
 
Регистрация: 15.12.2009
Сообщений: 69
По умолчанию Какой алгоритм решения задачи?

Дано N (1<=N<=100) пронумерованных объектов, которые охраняются и соединены K переходами (1<K<4950).
С любого объекта на любой другой можно пройти переходами. Идти по каждому переходу можно в обе стороны. Необходимо поместить пост милиции так, чтобы минимизировать расстояние от поста до самого дальнего объекта. Пост должен находится на одном из объектов. Напишите программу, которая находит оптимальное место для поста.
ВХОДНОЙ ФАЙЛ :
Вход: в первой строке натуральные числа N и K. В следующих K строках расположены по три натуральных числа F, T, S (объекты с номерами F и T соединены переходом длиной S метров, 1<S<10000; между F и T может быть не более одного прямого перехода)
ПРИМЕР :
Вход:
3 2
1 2 100
1 3 200
Выход:
200 1
ФАЙЛ ВЫХОДНЫХ ДАННЫХ :
Выход: в одной строке число D (расстояние до самого удаленного объекта) далее номер объекта, где расположен пост.
Если оптимальных мест расположения несколько выведите их все в порядке возрастания номеров (в той же строке).

У меня в голове лишь вариант алгоритма Дейкстры (для неотрицательных весов). Но, что-то останавливает. Подскажите может я не туда капаю?
Lodyr вне форума Ответить с цитированием
Старый 18.12.2020, 14:11   #2
kruta
Новичок
Джуниор
 
Регистрация: 18.12.2020
Сообщений: 1
По умолчанию

Алгоритм Флойда
kruta вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм решения задачи Amet13 Помощь студентам 1 21.04.2012 13:16
Каков алгоритм решения задачи? NeoMurderer Общие вопросы C/C++ 3 16.03.2012 21:45
Алгоритм решения задачи snpccvs Помощь студентам 8 13.02.2012 22:50
Нужен алгоритм решения задачи!!!!!! Катя21 Помощь студентам 2 03.01.2012 13:14
Какой алгоритм используется для ПОИСКА РЕШЕНИЯ в Excel JulOl Помощь студентам 2 31.03.2010 11:59