Налог
URL первоисточника: http://ctddev.ifmo.ru/school/io/archive.html
Задачу добавил: alef
Успешно сдано решений: 13
Страна Флатляндия разделилась на <желтых> и <зеленых>. Каждый город теперь поддерживает одну из двух партий. Все города стали <желтыми> или <зелеными>. Каждая дорога соединяет пару различных городов, все дороги двунаправлены. Любые два города соединены не более чем одной дорогой. Теперь купля-продажа товара возможна только между одноцветными городами. Транспортировка так же осуществляется между одноцветными городами, но так как, возможно, не
все пары одноцветных городов соединены дорогами провоз осуществляется через промежуточные города. При провозе товара через город цвета, отличного от цвета городов начала и конца пути, товар облагается налогом в 3 флатляндских евро. Так же необходимо уплачивать 1 флатляндский евро за проезд по любой дороге.
Ваша задача определить средний налог при провозе товара между каждой парой одноцветных городов. Разумеется, если путей между данной парой несколько, то выбирается путь с минимальным налогом. Гарантируется, что по дорогам можно проехать из любого города в любой другой.
Формат входного файла
В первой строке записаны два целых числа N, M (3<=N<=1000, N-1<=M<=5000), где N
- количество городов в стране, M - количество дорог. Пусть все города пронумерованы от 1 до N. Во второй строке содержится строка из N символов. i-ый символ строки равен Y если город поддерживает <желтых> и G если <зеленых>. В следующих M строках записаны дороги номерами соединяемых городов.
Формат выходного файла
Выведите искомое значение с округлением до 5 знаков после запятой.
Пример входного файла
5 5
YYGYG
1 2
5 1
3 4
3 2
5 4
Пример выходного файла
4.00000