Soutěž: Machr na algoritmy - Hledání cest

V tomto machrovi budeme pokračovat v hraní s městy. Tentokrát je však nebudete generovat, ale hledat v nich cesty. Vaším úkolem bude napsat aplikaci, která dostane na standardním vstupu popis města a dotazy na cesty a bude na tyto dotazy odpovídat. Vstup bude vypadat následovně:

počet_ulic_(n)
počet_křižovatek_(m)
název_první_ulice délka_první_ulice
název_druhé_ulice délka_druhé_ulice
...
název_n-té_ulice délka_n-té_ulice
první_křižovatka
druhá_křižovatka
...
m-tá_křižovatka
počet_dotazů_(d)
první_dotaz
druhý_dotaz
...
d-tý_dotaz

Počty jsou celá kladná čísla, názvy ulic jsou tvořeny malými a velkými písmeny anglické abecedy, číslicemi a podtřžítky (např. "5_Maje"), délky ulic jsou kladná reálná čísla. Křižovatka je reprezentována seznamem ulic, které se na ní setkávají - na vstupu budou jejich názvy oddělené mezerami.
Město tvoří graf - ulice jsou hrany (každá ulice spojuje právě 2 různé křižovatky) a křižovatky jsou vrcholy. Žádné 2 křižovatky nejsou spojeny více než 1 ulicí.

Dotaz obsahuje popis dopravní situace a názvy ulic, mezi kterými má aplikace hledat cestu. Dopravní situace se skládá z uzavřených a "ucpaných" ulic. Uzavřenými ulicemi se projet nedá, v ucpaných se tvoří kolony a jejich průjezd je 4× pomalejší. Popis situace v dotazu obsahuje pouze změny oproti minulému dotazu / počátečnímu stavu města. Dotaz tedy vypadá následovně:

počet_změn_dopr._situace_(s)
první_změna název_ulice
druhá_změna název_ulice
...
s-tá_změna název_ulice
startovní_ulice
cílová_ulice

změna je ve formátu "+ b/c" nebo "-"
'+' znamená přidání dopravní komplikace, '-' odebrání
'b' značí ucpanou ulici, 'c' uzavřenou
Pozn.: Změny probíhají v pořadí, v jakém jsou uvedeny na vstupu.

Na výstup bude aplikace vypisovat nalezené cesty jako posloupnosti názvů ulic (oddělené mezerami - každou cestu na samostatný řádek). Za název poslední ulice ještě vypíše délku nalezené cesty (u startovní a koncové ulice se do celkové délky cesty započítává jen polovina jejich délek). Pokud cesta nebude existovat, vypíšete na daný řádek pomlčku ('-'). Samozřejmě nechceme libovolnou cestu, ale tu nejrychlejší (co nejmenší suma délek ulic, ucpané ulice považujeme za 4× delší), pokud takových existuje více, vypište libovolnou z nich.
Pokud bude chybně zadaný vstup (text místo čísla, nepovolený znak v názvu ulice, ...), vypíšete vykřičník ('!') - pokud je chyba v dotazu, pokračujete dalším dotazem (chybný dotaz přeskočíte jako by neexistoval), je-li chyba v popisu města, ihned skončíte.

---

1. Ukázka
Vstup:

3
2
5_Maje 8
Americka 5.3
Boticska 14.7
5_Maje Americka
5_Maje Boticska
2
1
+c 5_Maje
Boticska
Americka
1
- 5_Maje
Boticska
Americka

Výstup:

-
Boticska 5_Maje Americka 18

2. Ukázka
Vstup:

x

Výstup:

!

Upozornění: programy budou automaticky testovány - výstup tedy musí přesně odpovídat popsanému formátu.

---

Hodnotit se bude primárně efektivita zvoleného algoritmu a správnost výstupů, okrajově kvalita (a přehlednost) kódu.

Větší ukázkový vstup: https://www.dropbox.com/…t/example.in?dl=0
Očekávaný výstup: https://www.dropbox.com/…/example.out?dl=0

Dotazy k zadání můžete psát do komentářů.