Shortest Routes I

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.

Example:

Input:  n = 3, m = 4,edges = {{1, 2, 6}, {1, 3, 2}, {3, 2, 3}, {1, 3, 4}}
Output: 0 5 2 

Approach

C++

#include <bits/stdc++.h>
using namespace std;
#define INF 100000000000000000
vector<pair<long long int, long long int>> arr[100001];
int main()
{

    long long int n = 3, m = 4;
    vector<vector<int>> edges = {{1, 2, 6},
                                 {1, 3, 2},
                                 {3, 2, 3},
                                 {1, 3, 4}};
    for (long long int i = 0; i < m; i++)
    {
        long long int a = edges[i][0];
        long long int b = edges[i][1];
        long long int w = edges[i][2];

        arr[a].push_back({b, w});
    }
    priority_queue<pair<long long int, long long int>,
                   vector<pair<long long int, long long int>>,
                   greater<pair<long long int, long long int>>>
        q;
    vector<long long int> dist(n + 1, INF);
    q.push({0, 1});
    dist[1] = 0;
    while (!q.empty())
    {
        long long int curr = q.top().second;
        long long int curr_d = q.top().first;
        q.pop();
        if (curr_d != dist[curr])
            continue;
        for (pair<long long int, long long int> edge : arr[curr])
        {
            if (curr_d + edge.second < dist[edge.first])
            {
                dist[edge.first] = curr_d + edge.second;
                q.push({dist[edge.first], edge.first});
            }
        }
    }
    for (long long int i = 1; i <= n; i++)
        cout << dist[i] << " ";

    return 0;
}