Cacher is the code snippet organizer for pro developers

const int MAX = 10000;
vector<pair<int,int> > adj[MAX]; // pair node, cost
int dijkstra( int s, int t, int dist[MAX] ) { // untested code
	memset( dist , 0x3f , sizeof dist ); // infinite distance
	dist[s] = 0;
	priority_queue< pair<int,int> > heap;
	heap.push( make_pair(0, s ) );
	while ( ! heap.empty()) {
		pair<int,int> cur = heap.top();
		heap.pop();
		int v = cur.second;
		int d = -cur.first;
		if ( d != dist[v] )    // priority_queue doesn’t support decrease_key
			continue;
		for (size_t i = 0 ; i < adj[v].size(); i++) {
			int newD = d + adj[v][i].second;
			int w = adj[v][i].first;
			if ( dist[w] > newD)
				heap.push(make_pair( - newD, w ) );			
		}
	}
	return dist[t];
}