Shortest Routes II

There are n cities and m roads between them. Your task is to process q queries where you have to determine the length of the shortest route between two given cities.

Example:

Input: n = 4, m = 3, q = 5, edges = {{1, 2, 5}, {1, 3, 9}, {2, 3, 3}},queries = {{1, 2}, {2, 1}, {1, 3}, {1, 4}, {3, 2}}

Output:

5
5
8
-1
3

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
int main()
{
    long long int n = 4, m = 3, q = 5;
    vector<vector<long long int>> edges = {{1, 2, 5},
                                           {1, 3, 9},
                                           {2, 3, 3}};

    vector<vector<long long>> queries = {{1, 2},
                                         {2, 1},
                                         {1, 3},
                                         {1, 4},
                                         {3, 2}};
    long long int dist[n + 1][n + 1];
    for (long long int i = 1; i <= n; i++)
    {
        for (long long int j = 1; j <= n; j++)
        {
            if (i != j)
                dist[i][j] = INF;
            else
                dist[i][j] = 0;
        }
    }
    for (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];

        dist[a][b] = min(w, dist[a][b]);
        dist[b][a] = min(w, dist[b][a]);
    }
    for (long long int k = 1; k <= n; k++)
    {
        for (long long int i = 1; i <= n; i++)
        {
            for (long long int j = 1; j <= n; j++)
            {
                if (dist[i][j] > dist[i][k] + dist[k][j])
                {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    for (int i = 0; i < q; i++)
    {
        long long int l = queries[i][0], r = queries[i][1];

        if (dist[l][r] == INF)
            cout << -1 << "\n";
        else
            cout << dist[l][r] << "\n";
    }
    return 0;
}