Олимпиадный тренинг

Задача . Острова


Задача

Темы:
Петя разрабатывает компьютерную игру. Игровое поле состоит из 11 островов, обозначенных латинскими буквами от A до K. На острове A стоит замок Героя. Некоторые острова соединены мостами. В рамках одного из заданий Герой должен обойти часть (возможно все) острова и собрать дань с их жителей. При этом, если Герой проходит по мосту, соединяющему два острова, мост рушится и больше по нему пройти нельзя. Задание считается выполненным только, если Герой возвращается на остров со своим замком. Информацию об игровом поле Петя хранит в базе данных, содержащей, в частности, две таблицы: Острова и Мосты. Каждая запись в таблице «Острова» хранит сведения об уникальном идентификаторе записи, названии острова и объеме дани, которую можно собрать с его жителей. Каждая запись таблицы «Мосты» хранит сведения об уникальном идентификаторе записи и двух идентификаторах островов, если между этими островами есть мост.
Петя посмотрел на текущие записи в таблицах:
Острова
ID Название Дань
1 A 0
2 B 20
3 C 10
4 D 20
5 E 70
6 F 10
7 G 20
8 H 30
9 I 30
10 J 50
11 K 30
 
Мосты
ID ID острова 1 ID острова 2
1 1 7
2 1 11
3 2 4
4 3 10
5 4 6
6 4 11
7 5 7
8 7 10
9 8 10
10 9 11

Проанализировав записи, Петя понял, что Герой не сможет выполнить задание. Тогда он добавил Герою возможность в рамках выполнения задания построить один новый мост, связав любые два острова. Определите, какой мост нужно построить, чтобы в результате Герой выполнил задание и при этом собрал максимальную дань. В ответе укажите подряд без пробелов сначала два символа, обозначающие названия островов, которые свяжет новый мост (отсортировав их по возрастанию), а затем число – дань, которую соберет Герой, выполнив задание.
 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя