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

Задача . Delivery Route


Задача

Темы: графы

У Фермера Джона N (1 <= N <= 100) ферм. Они расположены на 2D-плоскости в позициях (xi,yi), различных для всех ферм, xi и yi - целые числа.
ФД нуждается в Вашей помощи для планирования развозки материалов на N ферм. Начиная с фермы 1 он планирует посещать фермы последовательно (ферма 1, ферма 2, ферма 3, :) и после посещения фермы N вернуться на ферму 1. ФД требуется одна минута, чтобы сделать один шаг на север, юг, восток или запад. Кроме того, ФД хочет посетить каждую ферму ровно 1 раз во время путешествия (конечно, кроме фермы 1, которую он посетит дважды).
Помогите ФД определить минимальное количество времени, которое у него займет весь маршрут.
PROBLEM NAME: delivery
Формат входных данных
* Строка 1: Количество ферм, N.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа, xi yi (1 <= xi, yi <= 1,000,000).
Формат выходных данных
* Строка 1: Минимальное количество времени, которое требуется ФД, чтобы совершить свой путь или -1, если невозможно построить такой путь, чтобы каждую ферму (кроме фермы 1) посетить ровно 1 раз.
Примечание
ФД может совершить свой путь за 12 минут: 2 минут от фермы 1 к ферме 2, 5 минут от фермы 2 к ферме 3 (обходя ферму 1), 3 минуты от фермы 3 к ферме 4, 2 минуты вернуться к ферме 1.
Примеры
№Входные данныеВыходные данные
1 
4
2 2
2 4
2 1
1 3
 
12
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет