dijkstra.cpp

/***Dijkstra's Algorithm***/

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, int> PII;
#define MAX 1000
vector<PII> adj[MAX];
bool marked[MAX];
int dist[MAX];

void dijkstra(int s)
{
    priority_queue<PII, vector<PII>, greater<PII> > pq;
    memset(marked, false, sizeof marked);
    for(int i=1; i<MAX; i++) dist[i] = 1e9;

    PII p;
    pq.push(make_pair(0, s));
    dist[s] = 0;

    while(!pq.empty()){
        p = pq.top();
        pq.pop();

        int u = p.second;
        int cost_u = p.first;
        if(marked[u]) continue;

        marked[u] = true;

        for(int i=0; i<adj[u].size(); i++){
            int cost_u_to_v = adj[u][i].first;
            int v = adj[u][i].second;
            if(dist[v] > cost_u + cost_u_to_v){
                 dist[v] = cost_u + cost_u_to_v;
                 pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main()
{
    int nodes, edges;
    scanf("%d %d", &nodes, &edges);
    for(int i=0; i<edges; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(make_pair(w, v));;
    }
    dijkstra(0);
    for(int i=1; i<MAX; i++) printf("%d %d\n", i, dist[i]);
}