Time to Cycle

Saman is a cyclist and he needs to travel to several cities. He knows the roads between the cities and how long it takes to travel along each road. Help Saman calculate the time it will take to reach all cities from his starting location. Note: All roads are bidirectional

Input Format

The first line contains t, the number of test cases.

Each test case is as follows: - The first line contains two space-separated integers n and m, the number of cities and roads. - Each of the next lines contains three space-separated integers x, y, and r, the beginning and ending cities of an road, and the length of the road. - The last line of each test case has an integer s, denoting the starting city.

Constraints

Output Format

For each of the t test cases, print a single line consisting n-1 space separated integers denoting the shortest distance to the n-1 cities from the starting city s in increasing order of their labels, excluding s.

For unreachable nodes, print -1.

Sample Input 0

1
5 3
1 2 10
1 3 6
2 4 8
2

Sample Output 0

10 16 8 -1

Solution

Solution by Nirmal Bandara

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// Build adjacency list
vector<vector<vector<int>>> constructAdj(vector<vector<int>> &edges, int V) {
    vector<vector<vector<int>>> adj(V);
    for (auto &edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int wt = edge[2];
        adj[u].push_back({v, wt});
        adj[v].push_back({u, wt});
    }
    return adj;
}

// Dijkstra's algorithm
vector<int> dijkstra(int V, vector<vector<int>> &edges, int src) {
    vector<vector<vector<int>>> adj = constructAdj(edges, V);
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    vector<int> dist(V, INT_MAX);

    pq.push({0, src});
    dist[src] = 0;

    while (!pq.empty()) {
        int u = pq.top()[1];
        pq.pop();

        for (auto &x : adj[u]) {
            int v = x[0], weight = x[1];
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    int numOfCases;
    cin >> numOfCases;
    while (numOfCases-- > 0) {
        int numOfCities, numOfRoads;
        cin >> numOfCities >> numOfRoads;
        vector<vector<int>> edges;

        for (int i = 0; i < numOfRoads; i++) {
            int cityA, cityB, length;
            cin >> cityA >> cityB >> length;
            // Convert 1-based to 0-based
            edges.push_back({cityA - 1, cityB - 1, length});
        }

        int startCity;
        cin >> startCity;
        startCity--;  // Convert to 0-based
        vector<int> result = dijkstra(numOfCities, edges, startCity);

        // Output distances in 1-based order, excluding the source
        for (int i = 0; i < numOfCities; i++) {
            if (i == startCity) continue;
            if (result[i] == INT_MAX)
                cout << -1 << " ";
            else
                cout << result[i] << " ";
        }
        cout << endl;
    }
    return 0;
}