[NEW] Add solution for Shortest Route I

[AnjaliPai16]

🎯 Problem Information

• Problem Name: Shortest Route 1
• CSES Link: https://cses.fi/problemset/task/1671
• Category: Graph Algorithms
• Estimated Difficulty: [medium]

📋 Problem Description

There are n cities and m flight connections between them. Your task is to determine the length of the shortest route from Syrjälä to every city.

The first input line has two integers n and m: the number of cities and flight connections. The cities are numbered 1,2,....,n, and city 1 is Syrjälä.
After that, there are m lines describing the flight connections. Each line has three integers a, b and c: a flight begins at city a, ends at city b, and its length is c. Each flight is a one-way flight.
You can assume that it is possible to travel from Syrjälä to all other cities.

Print n integers: the shortest route lengths from Syrjälä to cities 1,2,....,n.

💡 Proposed Approach

Describe the algorithm/approach you plan to use:
I plan to use Dijkstra’s Algorithm with a priority queue (min-heap) to efficiently compute the shortest path from the source node (city 1) to all other nodes in a directed weighted graph.

Step-by-step plan:
1)Represent the graph using an adjacency list: adj[a].push_back({b, c})
2)Initialize a distance array dist[] with infinity (INF = 1e18) and set dist[1] = 0.
3)Use a min-heap priority queue to always pick the city with the smallest current distance.
4)For each node, relax all outgoing edges:
If dist[u] + w < dist[v], update dist[v] and push it into the queue.
5)Continue until the queue is empty, ensuring each node’s shortest distance is finalized.
6)Print the final distances for all cities in order.

• Time Complexity: O((n+m)log n), Each node and edge is processed once with a logarithmic heap update
• Space Complexity: O(n+m), For adjacency list and distance tracking.

📝 Implementation Notes

Any special considerations or optimizations needed:

• Requires fast I/O
• Needs modular arithmetic
• Large input constraints
• Edge cases to consider

🏷️ Labels

Please add appropriate labels:

• hacktoberfest (if contributing during Hacktoberfest)
• good first issue (if suitable for beginners)
• help wanted (if you need assistance)

👤 Assignee

• I would like to work on this issue
• I'm available for guidance/review

📎 Additional Context

Add any other context or screenshots about the problem here.

[shubhanshu2103]

Hello! I would like to work on this issue.
As detailed in the issue description, my plan is to implement Dijkstra's algorithm using a priority queue for an efficient O((n+m)log n) solution, incorporating fast I/O to handle the constraints.
If this approach looks good, could you please assign this to me? Thanks!

[ks-iitjmu]

@AnjaliPai16 Assigned