Solution 4 for Scaler Topics Fortnightly Contest - 4

This article is part of the Scaler Topics Fortnightly Contest - 4.

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

• Since we need to find the minimum time required to reach city A, we can modify dijktras to get the required time.
• For each city we maintain the following two states:

1. Minimum time required to reach city i, such that the parity of potions used is 0. We store it in state dist[i][0].
2. Minimum time required to reach city i, such that the parity of potions used is 1. We store it in state dist[i][1].

• So we can perform simple dijktras using the two states i.e., dist[i][0] and dist[i][1]. The answer would be stored at dist[A][0].

Time complexity: O(V + ElogV), where V is the number of vertices and E is the number of edges.

Extra memory complexity: O(V), for storing vertices while performing dijktras.

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation