Programozás‎ > ‎Feladatok‎ > ‎

Csatorna

Egy szennyvíz csatorna hálózathoz takarító robotot fejlesztettek. A hálózat csomópontokból és közöttük levő kör keresztmetszetű csatorna szakaszokból áll, amelyeknek ismerjük a csőátmérőjét. A robot olyan csövet tud tisztítani, amelynek átmérője nagyobb a robot méreténél. A robot a csatornában mindkét irányban haladhat. 

Feladat

Készíts programot, amely megadja, hogy adott pontból indítva a robot hány csatorna szakaszt tud kitisztítani, valamint hogy minimum hány további pontból kellene elindítani, hogy az összes olyan csatornát kitisztítsa, ahova befér!

Bemenet

A csatorna.be szöveges állomány első sora a csomópontok N számát (1≤N≤1000), a csatorna szakaszok M számát (1≤M≤10 000), a kiinduló csomópont sorszámát (1≤S≤N) és a robot R méretét (1≤R≤100) tartalmazza, egy-egy szóközzel elválasztva. A következő M sor mindegyike egy-egy csatorna szakasz két végpontját (1≤Ki≠Vi≤N) és átmérőjét (1≤Ai≤100) tartalmazza.

Kimenet

A csatorna.ki szöveges állomány első sorába az S pontból kitisztítható csatorna szakaszok számát kell írni! A második sorba azon további pontok minimális számát kell írni, amelyekből elindulva az összes olyan csatorna kitisztítható, ahova a robot befér!

Példa

Bemenet  Kimenet
12 15 4 10
1 2 11
5 8 1
1 3 11
1 4 1
2 5 11
6 7 1
3 6 1
4 7 11
4 8 11
4 5 1
8 7 11
11 7 10
8 12 11
9 10 1
11 10 11
4
2


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013, 11-13. évfolyam, döntő
Algoritmusok: