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;
}