Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi kategória, 2019. december 8.

2019. december 8. 10:15 – 2019. december 8. 15:15

Tima Xentopiába utazik


A kép forrása: WikiImages.

Xentopia városa kiterjedt vasúthálózattal rendelkezik. A városban N csomópont van, amelyeket 1-től N-ig számozunk. A csomópontokat M sínpár köti össze egymással. Minden sínpáron mindkét irányban közlekedhetnek a vonatok. Az egyes sínpárokat piros, kék vagy fehér színnel címkézzük.

Tima egy turista a városban, aki a lehető legrövidebb idő alatt szeretne eljutni az S csomópontból a T csomópontba. A célja eléréséhez használhatja a vasúthálózat térképét.

Tima meglehetősen excentrikus személyiség, ezért szabott magának egy érdekes feltételt: pontosan k1 piros, k2 kék és tetszőleges számú fehér sínpár igénybevételével szeretne utazni. A különböző színű sínpárok sorrendje tetszőleges lehet, és ugyanazt a sínpárt többször is felhasználhatja.

A feladatod, hogy meghatározd azt a minimális időt, amennyi ahhoz szükséges, hogy Tima eljusson S-ből T-be az általa szabott feltétel betartásával.

A bemenet specifikációja

A bemenet első sorában négy, szóközzel elválasztott egész szám szerepel: N (1 ≤ N ≤ 450), M (1 ≤ M ≤ 1 100), k1 és k2 (0 ≤ k1k2 ≤ 800, k1 · k2 ≤ 800). Ezt M sor követi, amelyek mindegyike szintén négy, szóközzel elválasztott egész számot tartalmaz U V X C formában, ahol U és V két olyan csomópont, amelyek között létezik sínpár (1 ≤ UV ≤ N, U ≠ V), ezt a távolságot a vonat X másodperc alatt teszi meg (0 ≤ X ≤ 109), és a sínpár C színnel van címkézve (0 ≤ C ≤ 2). Fehér sínpár esetén C = 0, piros sínpár esetén C = 1, míg kék sínpár esetén C = 2.

Az utolsó sorban két, szóközzel elválasztott egész szám szerepel: S (1 ≤ S ≤ N) és T (1 ≤ T ≤ N), amelyek rendre Tima utazásának forrás és cél csomópontját adják meg. Megjegyezzük, hogy S és T azonosak is lehetnek.

A kimenet specifikációja

A kimenetre egyetlen egész számot kell kiírni, amely Tima utazásának összidejét adja meg. Ha Tima nem tud eljutni a célba pontosan k1 piros, k2 kék és tetszőleges számú fehér sínpáron keresztül, akkor –1-et kell kiírni.

1. példa bemenet

  1. 4 4 1 1
  2. 1 2 1 2
  3. 1 3 1 0
  4. 2 4 1 1
  5. 3 4 1 0
  6. 1 4
letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

  1. 2
letöltés szöveges állományként

2. példa bemenet

  1. 4 3 200 1
  2. 1 2 1 1
  3. 2 3 1 0
  4. 2 4 1 2
  5. 1 3
letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

  1. -1
letöltés szöveges állományként

Eredeti feladat

ICPC North Central North America Regional Programming Contest, 2019

Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.