Az S. 140. feladat (2020. január)

S. 140. Egy titkosszolgálatnak \(\displaystyle N\) db számítógépe van, melyek közül néhányat kétirányú adatátvitelt biztosító kábelek kötnek össze, melyekből legfeljebb \(\displaystyle M\) db van. Az \(\displaystyle i\)-edik kábelnek öt fontos tulajdonsága van: \(\displaystyle a_{i}\), \(\displaystyle b_{i}\), \(\displaystyle t_{i}\), \(\displaystyle x_{i}\), \(\displaystyle y_{i}\), mely azt jelenti, hogy az \(\displaystyle a_{i}\) és \(\displaystyle b_{i}\) sorszámú számítógépek között egy információcsomag átküldése \(\displaystyle t_{i}\) időbe telik. Hogy biztonságosabbá tegyék a rendszert a hackertámadásokkal szemben, felváltva \(\displaystyle x_{i}\) ideig engedélyezik, majd \(\displaystyle y_{i}\) ideig megtiltják az adatátvitelt az \(\displaystyle i\)-edik kábelen. Kezdetben minden kábelen engedélyezve van az adatátvitel. Két számítógép között csak akkor küldhetünk át egy információcsomagot, ha a küldéstől a megérkezésig minden időpillanatban engedélyezve van az adott kábelen az adatátvitel. A \(\displaystyle K\)-adik számítógépről szeretnénk egy csomagot küldeni a \(\displaystyle V\)-edik számítógépre. Adjuk meg, hogy a csomag leghamarabb mikor érhet oda.

Standard bemenet: az első sor tartalmazza a számítógépek \(\displaystyle N\) számát, a kábelek \(\displaystyle M\) számát, valamint a \(\displaystyle K\) és \(\displaystyle V\) számítógépsorszámokat. Ezután \(\displaystyle M\) sor következik, ahol az \(\displaystyle i\)-edik sor tartalmazza az \(\displaystyle a_{i}\), \(\displaystyle b_{i}\), \(\displaystyle t_{i}\), \(\displaystyle x_{i}\), \(\displaystyle y_{i}\) számokat ebben a sorrendben.

Standard kimenet: adjuk meg, hogy leghamarabb mikor juthat el egy információcsomag a \(\displaystyle K\)-adik számítógépről a \(\displaystyle V\)-edik számítógépre. Ha nem juttatható el az információcsomag, akkor -1-et írjunk ki.

Példa:

Korlátok: \(\displaystyle 2\le N\le {10}^{5}\), \(\displaystyle 1\le M\le {10}^{6}\), \(\displaystyle 1\le t_{i}\), \(\displaystyle x_i,y_i\le {10}^{9}\), \(\displaystyle 1\le a_{i}, b_{i}, K, V\le N\). Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 1000\).

Beküldendő egy s140.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2020. február 10-én LEJÁRT.

Statisztika:

6 dolgozat érkezett.
10 pontot kapott:	Noszály Áron, Szente Péter, Varga 256 Péter.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2020. januári informatika feladatai