Solution 4 for Scaler Topics Fortnightly Contest - 11

This article is part of the Scaler Topics Fortnightly Contest - 11

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

• Clearly we cannot apply normal Dijkstra algorithm here.
• We need to apply some modification of it.
• Let us suppose there are two paths one from B to z.
• Path 1: From B to x and then x to z, and
• Path 2: From B to y and then y to z.
• Suppose Both the paths are of equal weights.
• Then in our modified Dijkstra algorithm, we will pick the edge, which has
• Lesser weight of the last edge. (Proof is left as an exercise for the reader).

Time Complexity: O(Mlog(A)).
Space Complexity: O(A + M).

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation