Weighted shortest path (1)

Go to the Jutge statement of the problem

Write a program that, given a directed graph with positive costs at the arcs, and two vertices x and y, computes the minimum cost to go from x to y.

“I don’t know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras.” - Alan Kay

(some context for the quotation)

Input: Input consists of several cases. Every case begins with the number of vertices n and the number of arcs m. Follow m triples u\ v\ c, indicating that there is an arc u \rightarrow v of cost c, where u \neq v and 1 \leq c \leq 10^4. Finally, we have x and y.
Assume 1 \leq n \leq 10^4, 0 \leq m \leq 5n, and that for every pair of vertices u and v there is at most one arc of the kind u \rightarrow v. All numbers are integers. Vertices are numbered from 0 to n−1.

Output: For every case, print the minimum cost to go from x to y, if this is possible. If there is no path from x to y, state so.

Hint

For this exercise a basic implementation of Dijkstra’s algorithm is enough.

A possible C++ code to start the problem

//Weighted Shortest path - 1
#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

using vertex = int;
using graph = vector<vector<pair<vertex,int>>>;// for the adjacency list of a weighted directed graph
using P = pair<int,vertex>; //distance, vertex

vector<int> dijkstra(const graph& g, vertex s){
    int n = g.size();
    vector<int> D(n, INT_MAX);//for all the distances from s
    vector<bool> marked(n,false);//for the visited vertices

    // here goes Dijkstra

    return D;
} 

int main(){
    int n, m;
    while(cin >> n >> m){
        graph g(n);
        for (int k = 0; k < m; ++k){
            int u, v, c;
            cin >> u >> v >> c;
            g[u].push_back({v,c});
        }
        vertex x, y;
        cin >> x >> y;
        vector<int> D = dijkstra(g, x);
        if (D[y] == INT_MAX) cout << "no path from " << x << " to " << y << endl;
        else cout << D[y] << endl;
    }
}

A possible solution

//Weighted Shortest path - 1
#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>

using namespace std;

using vertex = int;
using graph = vector<vector<pair<vertex,int>>>;// for the adjacency list of a weighted directed graph
using P = pair<int,vertex>; //distance, vertex

vector<int> dijkstra(const graph& g, vertex s){
    int n = g.size();
    vector<int> D(n, INT_MAX);
    vector<bool> marked(n,false);
    priority_queue<P, vector<P>, greater<P>> pq;
    D[s] = 0;
    pq.push({D[s],s});
    while (not pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if (not marked[u]){
            marked[u] = true;
            for (auto i : g[u]){
                vertex neigh = i.first;//the neighbor
                int w = i.second;// the weight
                if (D[neigh] > D[u] + w){
                    D[neigh] = D[u] + w;
                    pq.push({D[neigh],neigh});
                }
            }
        }
    }
    return D;
} 

int main(){
    int n, m;
    while(cin >> n >> m){
        graph g(n);
        for (int k = 0; k < m; ++k){
            int u, v, c;
            cin >> u >> v >> c;
            g[u].push_back({v,c});
        }
        vertex x, y;
        cin >> x >> y;
        vector<int> D = dijkstra(g, x);
        if (D[y] == INT_MAX) cout << "no path from " << x << " to " << y << endl;
        else cout << D[y] << endl;
    }
}

Other Links