# Dijkstra

## Problem:

Given a bidirectional graph of $N (1 \le N \le 50000)$ vertices and $M (N-1 \le M \le 100000)$ edges and the weight $w_i (0 \le w_i \le 1000)$ of each edge, find the shortest path from node $1$ to each node.

## Input (file.in):

Line $1$: Two integers, $N$ and $M$.
Lines $2 \ldots M+1$: Three integers, $a$, $b$, and $t$ that represent the weight of the edge between nodes $a$ and $b$ is $t$.

## Output (file.out):

Lines $1 \ldots N$: The distance from node $1$ to node $i$.

## Solution:

/*
* Example Dijkstra with Priority Queue and Adjacency List
* Albert Gural
*/

#include <fstream>
#include <vector>
#include <queue>

using namespace std;
FILE *fin  = fopen("file.in",  "r");
FILE *fout = fopen("file.out", "w");
int N, M, a, b, t; 	 // N = nodes, M = edges, t is dist from a to b
int 	dist[50005]; // distance from node 1
bool visited[50005]; // whether a node has been processed
vector<pair<int,int> > edges[50005]; // Adjacency List
vector<pair<int,int> >::iterator it;

int main () {
fscanf(fin, "%d %d", &N, &M);

// Initialize adjacency list with empty vectors.
for(int i = 0; i <= N; i++) {
vector<pair<int,int> > v;
edges[i] = v;
}

// Initialize distances (all but node 1 are at "infinity").
dist[1] = 0;
for(int i = 2; i <= N; i++)
dist[i] = 1000000000;

// Fill Adjacency list with data from input.
for(int i = 0; i < M; i++) {
fscanf(fin, "%d %d %d", &a, &b, &t);
edges[a].push_back(make_pair(b, t));
edges[b].push_back(make_pair(a, t));
}

// Initialize Priority Queue with first node.
// Priority Queue will be a collection of Pair<int, int>.
// First element gives distance from x to node 1.
// Second element gives x.
priority_queue<pair<int,int>, vector<pair<int, int> >,
greater<pair<int,int> > > q;
q.push(make_pair(0,1));

// Dijkstra
while(!q.empty()) {
int cur = q.top().second; 	// Current Node
int dcur = q.top().first; 	// Current Node's Distance
q.pop(); 					// Remove top element.
if(visited[cur]) continue;
visited[cur] = true;

// Look at each node adjacent to the current node.
// If the distance to those nodes + current distance is
// less than the current distance of those nodes, update it
// and add it to the queue.
for(it = edges[cur].begin(); it != edges[cur].end(); it++) {
int nextNode = (*it).first;  // Adjacent node to cur
int distNext = (*it).second; // Dist from adj. node to cur
if(dist[nextNode] > dcur + distNext) {
dist[nextNode] = dcur + distNext;
q.push(make_pair(dist[nextNode], nextNode));
}
}
}

// The shortest path from node 1 to all other nodes is
// now stored in the dist array.  Print each value of dist.
for(int i = 1; i <= N; i++)
fprintf(fout, "%d\n", dist[i]);
return 0;
}