Dijkstra's template for USACO

dijkstra.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define NUMV 1 // the maximum number of vertices
#define PROB_NAME "dijkstra" //replace with problem name
#define INF ~(1 << 31)

struct Node {
	Node (int index_, int length_) : index(index_), length(length_) {}
	int index, length;
	inline bool operator<(const Node& o) const {
		return length > o.length;
	}
};

int best[NUMV];
vector<Node> adj[NUMV];

// best[i] = keeps track of the best(shortest) distance from "start" to "i"
void djikstra(int start) {
	memset(best, INF, sizeof(int)*NUMV); // initialize to infinity
	best[start] = 0;
	priority_queue<Node> pq;
	pq.push(Node(start, 0));
	while (!pq.empty()) {
		Node curr = pq.top();
		pq.pop();
		if (curr.length > best[curr.index]) // if it's worse than what you already have, continue
			continue;

		// go throught the adjacency list
		for (vector<Node>::iterator it = adj[curr.index].begin(); it != adj[curr.index].end(); it++) {
			if (curr.length + it->length < best[it->index]) { // update if necessary
				best[it->index] = curr.length + it->length;
				pq.push(Node(it->index, best[it->index]));
			}
		}
	}
}

int main() {
	freopen(PROB_NAME + ".in", "r", stdin);
	freopen(PROB_NAME + ".out", "w", stdout);

	//CODE HERE

	return 0;
}