CSES | Shortest Routes I














































CSES | Shortest Routes I



CSES | Shortest Routes 1

Given n cities and m flights, the task is to find the shortest path from city 1 to every other cities.

This problem is the standard problem of Single Source Shortest problem and can be solved using Dijkstra's Algorithm.

Dijkstra's Algorithm:
Create a distance array of size n+1 and assign distance infinity to each vertex, other than source, and assign 0 to source.
This array denotes the distance of all vertex from the source.
In addition, we create a boolean array of size n+1, which denotes whether or not a particular vertex has been visited.
The Dijkstra's algorithm runs for n iterations, in each iteration, an unmarked vertex is chosen which has the minimum distance with the source. 
(OR instead of creating visited array and marking the vertices, we can store them in min_heap, and remove the minimum value in each iteration.)
Now the selected vertex is marked, let's say this vertex v. From vertex v, the relaxation is performed to all other vertices as follows -
                                        distance[u] = min(distance[u], distance[v]+length)
After all the n iterations, the algorithm terminates.

C++ Implementation of Shortest Routes 1 :

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+3;
const int inf = 1e18;
vector<vector<pair<int,int>>> adj(N, vector<pair<int,int>>());
vector<int> dist(N, inf);
 
void dijkstra() {
dist[1] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, 1});
while(!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if(dist[u] < d)
continue;
for(auto e : adj[u]) {
int v = e.second;
int c = e.first;
if(dist[v] <= c+d)
continue;
else {
dist[v] = c+d;
pq.push({dist[v], v});
}
}
}
}
 
int32_t main() {
int n, m;
cin >> n >> m;
 
for(int i = 1; i <= m; i++) {
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back({w, b});
}
dijkstra();
for(int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
return 0;
}


More Articles of Anuj Maurya:

Name Views Likes
C++ | Find smallest interval 222 0
C++ | Lexicographic rank of string 95 0
C++ | Counting Rooms (CSES) 92 0
C++ | Building Roads (CSES) 78 0
C++ | High Score (CSES) 199 0
C++ | Collect maximum coin in grid 75 0
C++ | Is this k-palindrome ? 75 0
C++ | Shuffle the array elements 64 0
C++ | Fizz Buzz 81 0
C++ | Check if given points form square 59 0
C++ | Klee Algorithm to find union of line segment 87 0
C++ | Check if points are collinear 75 0
C++ | Check if given point lies inside triangle 82 0
C++ | Check if two line segment intersect 78 0
C++ | Number of ways to decode message 74 0
C++ || Minimise the subset difference 60 0
C++ | Count of subsets with given sum 67 24
C++ | Currency Arbitrage 97 22
C++ | Estimating the value of π (pi) using Monte-Carlo Simulation 57 18
C++ | Find the first missing number 75 16
C++ | Finding word in grid using DFS 66 11
C++ | Implementing pow(x, y) in logarithmic time 52 9
C++ | Sum of all factors of number 80 10
C++ | Building Teams (CSES) 69 21
C++ | Positions of anagram 47 12
C++ | Integer factorization 55 13
C++ | Primality test 63 14
C++ | Subset Sum Problem 64 12
C++ | Civil Time in Abseil 66 19
C++ | Abseil Time Duration 119 15
C++ | absl::Time 92 12
C++ | Introduction to Abseil Time library 81 9
C++ | absl::StripPrefix() and absl::StripSuffix() 79 8
C++ | absl::ConsumePrefix() and absl::ConsumeSuffix() 92 19
C++ | absl::string_view 71 13
C++ | absl::Substitute() | Formatting string in abseil 84 15
C++ | absl::StrJoin() | Yet another way of joining strings 116 7
C++ | String concatenation in Abseil - 2 | absl::StrCat() 103 10
C++ | absl::StrAppend() | String concatenation in abseil - 1 78 16
C++ | absl::StrSplit() 149 15
C++ | Appending to string and Writing to stream in Abseil 86 11
C++ | absl::PrintF(), absl::FPrintF() and absl::SNPrintF() 96 0
C++ | Abseil StrFormat() 70 27
C++ | Abseil flags Library 122 348
C++ | Abseil Numeric Library 86 65
C++ | Abseil Hash library 81 0
C++ | Abseil Containers 139 46
C++ Introduction to Abseil 88 13
CSES | Shortest Route II 251 47
CSES | Shortest Routes I 187 1

Comments