|
0 / 0 / 0
Регистрация: 15.06.2016
Сообщений: 9
|
|
Подскажите по поводу задачи15.06.2016, 14:39. Показов 1086. Ответов 7
Метки нет (Все метки)
Товарищи,настигла беда,есть задача,когда смотрю на условие мозги кипят,помогите решить пожалуйста
Вот собственно условие: Вам предоставляется список городов . Каждая прямая связь между двумя городами имеет свою стоимость транспортировки (целое число больше 0 ) . Цель состоит в том , чтобы найти пути минимальной стоимости между парами городов . Предположим, что стоимость каждого пути ( которая является суммой расходов всех прямых соединений belongning к этому пути ) не более чем 200000. название города является строка, содержащая символы а, ..., Z и самое большее 10 символы long.2 ) input s [ количество тестов < = 10 ] п [ число городов < = 10000 ] NAME [ название города ] р [ число соседей NAME ] города Стоимость NR [ NR - индекс города , подключенного к NAME (индекс первого города 1)] [Стоимость - стоимость транспортировки ] г [ число путей , чтобы найти < = 100 ] NAME1 NAME2 [ NAME1 - источник , NAME2 - назначения ] [Пустая линия, разделяющая тесты ] Input: 1 4 Гданьск 2 2 1 3 3 Быдгощ 3 1 1 3 1 4 4 Торунь 3 1 3 2 1 4 1 Варшава 2 2 4 3 1 2 Гданьск Варшава Быдгощ Варшава
0
|
|
| 15.06.2016, 14:39 | |
|
Ответы с готовыми решениями:
7
Подскажите по поводу Color Class Подскажите по поводу кода(подбор чисел)
|
|
2399 / 2224 / 565
Регистрация: 28.12.2010
Сообщений: 8,672
|
|
| 15.06.2016, 17:12 | |
|
Lucem, задача похоже переведена с какого-то языка....а в целом обычная задача на графы. Задача коммивояжера
0
|
|
|
0 / 0 / 0
Регистрация: 15.06.2016
Сообщений: 9
|
|
| 16.06.2016, 11:14 [ТС] | |
|
спасибо,просто я даже не знал в какую сторону копать,буду разбираться
Добавлено через 17 часов 54 минуты посмотрел туториалы,про задачу коммивояжера,вроде разобрался. Но условие данной задачи до сих пор не вкурил. Вопрос такой:как может быть у г.Гданьска и Варшавы 2 соседа,а у остальных по 3 и скажите,по стоимости транспортировки,это какие в данном случае цифры? от Гданьска к Быдгощу 1 или 2?
0
|
|
|
155 / 154 / 53
Регистрация: 30.04.2016
Сообщений: 321
|
|
| 16.06.2016, 11:30 | |
|
Задача коммивояжера - это когда надо вернуться в начальную точку в конце и если обходить n точек, здесь наксолько я понял надо найти кратчайший путь между двумя точками - алгоритм дейкстры именно для такого случая.
Касательно условия, нарисуй на бумаге в виде графов данные, условие довольно понятное - опять же по ссылке которой я привел есть примеры графов.
1
|
|
|
0 / 0 / 0
Регистрация: 15.06.2016
Сообщений: 9
|
||||||
| 16.06.2016, 15:17 [ТС] | ||||||
|
вот некоторые мысли,если продолжить это решение и из одного метода передавать в другой результаты,пока не достигну последнего тавера
это будет очень глупое решение?
0
|
||||||
|
155 / 154 / 53
Регистрация: 30.04.2016
Сообщений: 321
|
|
| 16.06.2016, 15:30 | |
|
Очень плохая структура, а если понадобится 4 или 5 соседей, ты что будешь еще конструкторы и поля дописывать?
А метод, ты каждый раз обходишь все города, не отмечаешь уже пройденные.
0
|
|
|
0 / 0 / 0
Регистрация: 15.06.2016
Сообщений: 9
|
|
| 16.06.2016, 16:08 [ТС] | |
|
а есть ещё статьи для прочтения,по данной теме?)
0
|
|
| 16.06.2016, 16:08 | |
|
Помогаю со студенческими работами здесь
8
подскажите по поводу универа Подскажите по поводу подключения Подскажите по поводу vds Подскажите по поводу сборки Подскажите по поводу компонентов Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git
main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели
8ATzM_2aurI
|
Блокировка документа от изменений, если он открыт у другого пользователя
Maks 08.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2.
Задача: запретить редактирование документа, если он открыт у другого пользователя.
/ / . . .
|
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои.
А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
|
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20%
kYBz3eJf3jQ
|
|
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
|
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
|
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора
Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2.
Задача: уведомлять пользователя, если. . .
|
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2.
Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
|