https://youtu.be/EmMo7aTxInc?t=1m38s
szerk.: 3 Dijsktra?
Elsőnek úgy, hogy kiveszem belőle az összes speciális csúcsot (meg az azokból induló éleket), kivéve a start, s végpontot.
Másodjára úgy, hogy csak a speciális csúcsok közötti éleket veszem ki. (ugyancsak kivétel a kezdeti, s a végpont)
Harmadjára meg az eredeti gráfon.
Ha van út a speciális csúcsokon kívül, az első megtalálja.
Ha nincs, de elég egy speciális csúcsot érintenem (nem kell speciális csúcsból másik speciális csúcsba menni), akkor a második.
A harmadikhoz kell, hogy a speciális csúcsok között ne haladjon negatív súlyú él.
szerk2.: közben rájöttem, hogy nem lesz negatív él. bocs.
--
blogom