Ha a speciális csúcsokban O(1) a keresés ideje, akkor amikor egy csúcs szomszédai közt iterál a Dijkstra, egyszerűen megvizsgálnám, hogy benne van-e a speciális halmazban, és kihagynám.