UVa 341 - Non-Stop Travel

#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

// Implementation of Dijkstra's algorithm using adjacency lists
// and priority queue for efficiency.
// Running time: O(|E| log |V|)
// from Stanford ACM Team Notebook 2011-12
const int INF = 2147483647;
typedef pair<int, int> PII;
class Dijkstra {
private:
	int N;
	vector<vector<PII> > edges;
	vector<int> dist, dad;
public:
	Dijkstra(int number_of_nodes) {
		N = number_of_nodes;
		edges = vector<vector<PII> >(N);
	}
	void addEdge(int from, int to, int weight) {
		edges[from].push_back(make_pair(weight, to));
	}
	void run(int start_node) {
		// use priority queue in which top element has the "smallest" priority
		priority_queue<PII, vector<PII>, greater<PII> > Q;
		dist = vector<int>(N, INF);
		dad = vector<int>(N, -1);
		Q.push(make_pair(0, start_node));
		dist[start_node] = 0;
		while (!Q.empty()) {
			PII p = Q.top();
			//if (p.second == end_node)
			//break;
			Q.pop();
			int here = p.second;
			for (vector<PII>::iterator it = edges[here].begin(); it != edges[here].end(); it++) {
				if (dist[here] + it->first < dist[it->second]) {
					dist[it->second] = dist[here] + it->first;
					dad[it->second] = here;
					Q.push(make_pair(dist[it->second], it->second));
				}
			}

		};
	}
	int getDistanceTo(int end_node) {
		return dist[end_node];
	}
	vector<int> getPathTo(int end_node) {
		vector<int> path;
		for (int i = end_node; i != -1; i = dad[i]) {
			path.push_back(i);
		}
		reverse(path.begin(), path.end());
		return path;
	}
};

int main() {
	int number_of_nodes, number_of_neighbors, neighbor, weight, case_number = 0, start_node, end_node;

	while (cin >> number_of_nodes && number_of_nodes) {
		case_number++;

		Dijkstra dijkstra = Dijkstra(number_of_nodes);
		for (int i = 1; i <= number_of_nodes; i++) {
			cin >> number_of_neighbors;
			for (int j = 0; j < number_of_neighbors; j++) {
				cin >> neighbor >> weight;
				dijkstra.addEdge(i - 1, neighbor - 1, weight);
			}
		}
		cin >> start_node >> end_node;
		dijkstra.run(start_node - 1);
		cout << "Case " << case_number << ": Path =";

		vector<int> path = dijkstra.getPathTo(end_node - 1);
		for (int i = 0; i < path.size(); i++)
			cout << " " << path[i] + 1;

		cout << "; " << dijkstra.getDistanceTo(end_node - 1) << " second delay" << endl;
	}
	return 0;
}