АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Примеры входа и выхода. Задача 5. “Driving” (алгоритм Беллмана-Форда)

Читайте также:
  1. ALSt Состояние выхода сигнала АПС. CLOS или ОРЕn.
  2. II. Примеры, подтверждающие милость, явленную в Пророке, да благословит его Аллах и да приветствует.
  3. MS Excel.Текстовые функции, примеры использования текстовых функций.
  4. SCADA. Назначение. Возможности. Примеры применения в АСУТП. Основные пакеты.
  5. Активация точек входа и выхода энергетических нитей
  6. Аэропорт Москвы, у выхода для экипажа. Они идут
  7. Б) длительность одного полного кругооборота средств с момента их превращения из денежной формы в производственные запасы и до выхода готовой продукции и ее реализации
  8. БОЕВЫЕ ПРИМЕРЫ
  9. В поисках выхода: ответ на угрозы, связанные с нестабильностью сырьевых цен
  10. В ЧЛЕНЫ ТОВАРИЩЕСТВА И ВЫХОДА ИЗ НЕГО
  11. В. Примеры случайных процессов
  12. Взаимно исключающие связи в ER-модели. Примеры. Отображение диаграммы со взаимно исключающими связями в реляционную схему.
wormholes.in wormholes.out
2011 1956 1975 2005 IMPOSSIBLE  

 


Задача 5. “Driving” (алгоритм Беллмана-Форда)

Входной файл: driving.in

Выходной файл: driving.out

Ограничение времени: 1 секунда

Ограничение памяти: 64M байт

 

After a period of intensive development of the transportation infrastructure, the government of Ruritania decides to take firm steps to strengthen citizens' confidence in the national road network and sets up a compensation scheme for adventurous driving (CSAD). Those driving on a road with holes, bumps and other entertaining obstacles get compensation; those driving on a decent road pay tax. These compensations and taxes are obtained and paid in cash on entry on each road and depend on the entry point on the road. What you get and pay driving on a road from A to B may be different from what you get and pay driving on the same road from B to A. The Ruritarian authorities call fee the amount of money paid as tax or obtained as compensation on entry on a road. A positive fee is a tax; a negative fee stands for compensation.

John Doe plans to take advantage of CSAD for saving money he needs to repair his old car. When driving from A to B, John follows a path he calls optimal: a path that is rewarding and has the minimal length out of the paths with the minimal weight from A to B. In John's opinion, a path is rewarding if all the roads in the path are rewarding, and a road (X,Y) is rewarding if it has the minimal entry fee out of the roads leaving X. The weight of a path is the sum of the entry fees paid along the path. The length of a path cumulates the length of the roads in the path. The problem is helping John to compute the weight and the length of an optimal path from A to B on a given map.

 

Вход

Write a program that reads data set from a text file. Data set encodes a road map and starts with four integers: the number 1 ≤ n ≤ 100 of towns on the map, the number 0 ≤ m ≤ 5000 of roads, the departure town 0 ≤ A ≤ n-1, and the destination town 0 ≤ B ≤ n -1. Follow m data quintuples u, v, fuv, L, fvu, where u and v are town identifiers (integers in the range 0.. n -1), -100 ≤ fuv, fvu ≤ 100 are integer fees for driving on the road (u, v), and 1 ≤ L ≤ 100 is the integer length of the road. The quintuples may occur in any order. Input data are correct.

 

Выход

The program prints from the beginning of a line the weight and the length of an optimal path, according to John's oppinion, from A to B. If there is no optimal path from A to B the text VOID is printed. If the weight of the optimal path from A to B has no lower bound the text UNBOUND is printed.

 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)