Форум программистов, компьютерный форум, киберфорум
Java
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
15.06.2016, 14:39
Ответы с готовыми решениями:

Подскажите по поводу Color Class
Добрый день подскажите пожалуйста, я пишу программку которая определяет какой цвет получился из заданных трех цветов: красный, зеленый и...

Подскажите по поводу кода(подбор чисел)
Здравствуйте, вообщем хочу написать программу которая сможет вычислять пароль (из цифр), я только начал изучать программирование и еще...

Можете подсказать по поводу задачи?
Расчитать сумму членов бесконечного ряда с заданой пользователем точностью E для заданого поьзователем значения х(-1;1) :...

7
 Аватар для ninjacut
155 / 154 / 53
Регистрация: 30.04.2016
Сообщений: 321
15.06.2016, 17:04
Почитай про алгоритм Дейкстры.
0
Эксперт Java
 Аватар для KEKCoGEN
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
 Аватар для ninjacut
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  [ТС]
вот некоторые мысли,если продолжить это решение и из одного метода передавать в другой результаты,пока не достигну последнего тавера
это будет очень глупое решение?

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class Main {
public static void main(String[] args) throws IOException {
Tower tower = new Tower(1,2,2,1,3,3);
Tower tower1 = new Tower(2,3,1,1,3,1,4,4);
Tower tower2 = new Tower(3,3,1,1,3,1,4,4);
Tower tower3 = new Tower(4,2,2,4,3,1,2);
ArrayList<Tower>list = new ArrayList<>();
list.add(tower);
list.add(tower1);
list.add(tower2);
list.add(tower3);
}
public Map<Integer,Integer>getid(ArrayList<Tower>list)
{
Map<Integer, Integer>map = new LinkedHashMap<>();
for (int i = 0; i < list.size();i++)
{
if (list.get(i).id==1)
{
if (list.get(i).sosedi==2)
{
int a1 = list.get(i).id1soseda;
int cost1 = list.get(i).cost1;
int a2 = list.get(i).id2soseda;
int cost2 = list.get(i).cost2;
if (cost1<cost2)
{
map.put(a1,cost1);
}
else map.put(a2,cost2);
 
}
}
}
return map;
}
 
 
public static class Tower
{
int sosedi,id,id1soseda,cost1,id2soseda,cost2, id3soseda,cost3;
 
 
public Tower(int id, int sosedi, int id1soseda, int cost1, int id2soseda, int cost2) {
this.sosedi = sosedi;
this.id = id;
this.id1soseda = id1soseda;
this.cost1 = cost1;
this.id2soseda=id2soseda;
this.cost2=cost2;
 
}
public Tower(int id, int sosedi,int id1soseda, int cost1, int id2soseda,int cost2,int id3soseda,int cost3) {
this.sosedi = sosedi;
this.id = id;
this.id1soseda = id1soseda;
this.cost1 = cost1;
this.id2soseda=id2soseda;
this.cost2=cost2;
this.id3soseda=id3soseda;
this.cost3=cost3;
 
 
}
public Tower(int id, int sosedi,int id1soseda, int cost1, int id2soseda,int cost2,int id3soseda) {
this.sosedi = sosedi;
this.id = id;
this.id1soseda = id1soseda;
this.cost1 = cost1;
this.id2soseda=id2soseda;
this.cost2=cost2;
this.id3soseda=id3soseda;
 
 
}
}
}
0
 Аватар для ninjacut
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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
16.06.2016, 16:08
Помогаю со студенческими работами здесь

подскажите по поводу универа
хочу после 11 класса пойти в вуз в Москве с изучением делфи на программиста. Какие предметы егэ надо сдавать и какой из московских вузов...

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

Подскажите по поводу vds
Нужен vds c неограниченым траффиком, также планируется запускать каждые несколько минут многопоточные скрипты потоков в 10-20. До этого не...

Подскажите по поводу сборки
Собрал я в общем компьютер себе Мать Гигабайт GA-78lmt-usb3 Проц AMD FX 8300 в разгоне до 4ггц Видеокарта MSI Geforse gtx 1060 3 gb ...

Подскажите по поводу компонентов
Подскажите компоненты для создания списка слева и список торрентов по середине. Если это создано не с помощью чего-то готового - накидайте...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
модель ЗдравоСохранения 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. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru