ในข้อนี้ โจทย์สรุปเป็น variant หนึ่งของโจทย์ shortest path โดยจะต้องหาว่า ภายใต้งบ $Z$ นั้น การเดินทางจาก $X$ ไป $Y$ โดยเดินจาก $X$ ไปยัง $V$ แล้วให้จาก $Y$ มารับจาก $V$ ไป จะได้ระยะทางสั้นสุดจาก $Y$ ไปยัง $V$ เป็นเท่าใด หากเท่ากันหลายค่า ให้ตอบค่าที่ $V$ น้อยสุด

ในข้อนี้ เราจะใช้ Dijkstra's Algorithm ในการหา Shortest Path อย่างรวดเร็ว

สังเกตได้ว่าถ้าเราสามารถเดินทางโดยตรงจาก $X$ ไปยัง $Y$ ในงบ $Z$ เลยก็ง่าย คือเราจะทำเพียงหา Shortest Path จาก $X$ ไปยัง $Y$ ก็จะเสร็จสิ้น แต่หากไม่สามารถทำได้เราจำเป็นจะต้องหา $V$ ที่ $dist(X, V) \leq Z$ และ ภายใต้ $V$ เหล่านี้ จะต้องหา $\min\limits_{V}{dist(Y,V)}$

วิธีเบื้องต้นคือไล่หาทุกๆ $V$ ที่เป็นไปได้ แล้วหาระยะทางจาก $Y$ มายัง $V$ ซึ่งจะทำงานในเวลา $\mathcal{O}(NM \log N)$ ซึ่งไม่ทัน

วิธีที่ดีสำหรับข้อนี้ คือการเริ่มหา Single Source Shortest Path (SSSP) จาก $X$ ไปยังทุกจุดที่เป็นไปได้ เท่านี้เราจะทราบว่ามีจุดใดบ้างที่สามารถไปถึงได้ โดยการกรองเฉพาะจุดที่ระยะห่างจาก $X$ มีไม่เกิน $Z$ จุดเหล่านั้นคือค่าของ $V$ ที่เป็นไปได้ เพื่อความสะดวก จะเรียกเซตของจุดเหล่านั้นว่า $S$ ต่อมาทำ Single Source Shortest Path อีกครั้ง จาก $Y$ ไปยังแต่ละจุดในกราฟ แล้วพิจารณาเฉพาะ distance ของจุดในเซต $S$ แล้วค่อยๆหาจุดที่มี distance ต่ำสุด หากเท่ากันให้นับจุดที่มีหมายเลขต่ำกว่า เป็น $V$ ที่ต้องการ เท่านี้จะได้ตามที่โจทย์ต้องการ

Time Complexity: $\mathcal{O}(M \log N)$