Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_15_10 - Demonstracja 2

Władze stolicy właśnie dowiedziały się, że w najbliższym czasie planowane jest przejście ogromnej demonstracji. Miasto pełne jest zabytków i starych kamienic, które mogłyby ucierpieć w przypadku zamieszek, ale naszych polityków to nie obchodzi. Jedyne na czym im zależy to, aby demonstracja nie przeszła ulicami, na których znajdują się ratusz oraz sejm. W związku z powyższym urzędnicy negocjują właśnie z organizatorami trasę przemarszu.

Organizatorzy przedstawili sprawę jasno - chcą jedynie dotrzeć z punktu p do punktu k ponosząc przy tym jak najmniejszy koszt (w stolicy organizatorzy demonstracji muszą płacić za możliwość przejścia przez daną ulicę, wyznaczoną przez urząd miasta stawkę). Nic prostszego pomyśleli urzędnicy - wyznaczymy koszty przejścia przez ulice na których są ratusz i sejm w taki sposób, aby demonstracja je ominęła!

Po opracowaniu tej genialnej koncepcji (i otrzymaniu w związku z tym premii) urzędnicy zabrali się za... poszukiwanie osoby, która zrobi wszystko za nich i poprosili nas, aby umieścić to zadanie w AlgoLidze. Ocal polityków przed niechybnym obrzuceniem jajkami! Napisz program, który obliczy o ile należy podnieść koszt przejścia przez chronione ulice, aby zagwarantować, że nie znajdą się one na trasie przemarszu.

Wejście

W pierwszej linii wejścia znajdują się cztery liczby całkowite n, m, p, k (3 ≤ n ≤ 1000; 3 ≤ m ≤ 1500; 0 ≤ p, k < n; pk) określające odpowiednio liczbę skrzyżowań w mieście, liczbę łączących je ulic oraz numer skrzyżowania początkowego i końcowego trasy demonstracji.

W kolejnych m liniach znajdują się opisy ulic. Każdy opis składa się z trzech liczb a, b, c (0 ≤ a, b < n; ab; 1 ≤ c ≤ 100) oraz opcjonalnego wyrazu CHRONIONA, który wskazuje na to, że opis dotyczy ulicy, na której znajduje się sejm lub ratusz. Warto tutaj odnotować, że sejm i ratusz mogą znajdować się na tej samej ulicy. Liczby a i b określają numery skrzyżowań pomiędzy, którymi przebiega ulica, zaś liczba c określa stawkę jaką demonstranci muszą zapłacić miastu ze jej przejście.

Uwaga! Gwarantujemy, że jeżeli najtańsza droga z p do k prowadzi przez ulice, na których znajduje się sejm lub ratusz, to będzie istniała, co najmniej jeszcze jedna trasa pomiędzy tymi skrzyżowaniami.

Wyjście

Na wyjściu należy wypisać minimalną sumę kwot o jaką należy podnieść opłaty za przejście ulicami, na których znajduje się sejm i ratusz, tak aby na pewno nie przeszła tamtędy demonstracja.

Przykład

Wejście

8 9 0 7
0 1 1
0 2 1
0 3 1
1 4 1 CHRONIONA
4 7 1
2 5 1 CHRONIONA
5 7 1
3 6 3
6 7 2

Wyjście

8

Dodane przez:Maciej Boniecki
Data dodania:2014-03-29
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-03-29 17:13:08 Maciej Boniecki
Nie
2014-03-29 17:11:11 Jakub Staroñ
Czy między dwoma skrzyżowaniami może istnieć więcej niż jedna ulica?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.