USACO Platinum Problem #1 (http://usaco.org/index.php?page=viewproblem2&cpid=576) with time complexity O(n^2) (too slow)

maxflow.cpp

#include <algorithm>
#include <ctime>
#include <fstream>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// whether to use breadth-first search or dijkstra's algorithm
#define BFS_OR_DIJKSTRA true

// We have to use a multigraph to model the pipes and stalls
class node;
class edge;

class multigraph {
public:
	std::vector<node*> nodes;
	std::vector<edge*> edges;

	~multigraph();
	bool operator==(const multigraph&);
	void add_edge(edge* e);
};

class node {
public:
	std::vector<edge*> edges;
	// unique to this problem
	int pressure;

	node();
	bool operator==(const node&);
	void add_edge(edge* e);
};

class edge {
public:
	node* vertex1;
	node* vertex2;

	edge(node*, node*);
	bool operator==(const edge&);
};

multigraph::~multigraph() {
	for (node* n : nodes) {
		delete n;
	}
	for (edge* e : edges) {
		delete e;
	}
}

node::node() {
	pressure = 0;
}

edge::edge(node* v1, node* v2) {
	vertex1 = v1;
	vertex2 = v2;
}

bool multigraph::operator==(const multigraph& o) {
	return this == &o;
}

bool node::operator==(const node& o) {
	return this == &o;
}

void multigraph::add_edge(edge* e) {
	edges.push_back(e);
}

void node::add_edge(edge* e) {
	edges.push_back(e);
}

bool edge::operator==(const edge& o) {
	return this == &o;
}

std::vector<std::string> split_by_space(std::string s) {
	std::vector<std::string> result;
	std::stringstream ss(s);
	std::string item;
	while (std::getline(ss, item, ' ')) {
		result.push_back(item);
	}
	return result;
}

int main(int argc, char* argv[])
{
	// TODO DEBUG
	// time the program
	clock_t begin = clock();

	// problem parameters
	int n, k;
	multigraph graph;
	std::vector<std::pair<node*, node*>> endpoints;
	// we don't need to store the paths because we only use them once

	// Read in the input file
	std::ifstream input_file("maxflow.in");
	if (input_file.is_open()) {
		std::string line;

		// get first line N K
		if (std::getline(input_file, line)) {
			std::vector<std::string> split = split_by_space(line);
			n = stoi(split[0]);
			k = stoi(split[1]);
		}

		// create N nodes
		for (int i = 0; i < n; i++) {
			node* new_node = new node();
			graph.nodes.push_back(new_node);
		}

		// edges
		for (int i = 0; i < n - 1 && std::getline(input_file, line); i++) {
			std::vector<std::string> split = split_by_space(line);
			node* node1 = graph.nodes[stoi(split[0]) - 1];
			node* node2 = graph.nodes[stoi(split[1]) - 1];
			edge* e = new edge(node1, node2);
			node1->add_edge(e);
			node2->add_edge(e);
			graph.add_edge(e);
		}

		// endpoints
		for (int i = 0; i < k && std::getline(input_file, line); i++) {
			std::vector<std::string> split = split_by_space(line);
			node* endpoint1 = graph.nodes[stoi(split[0]) - 1];
			node* endpoint2 = graph.nodes[stoi(split[1]) - 1];
			endpoints.push_back(std::make_pair(endpoint1, endpoint2));
		}
	}
	input_file.close();

	// search
	// copy graph.nodes to a vector of pointers
	std::vector<node*> nodes;
	for (node* n : graph.nodes) {
		nodes.push_back(n);
	}
	// for each first point in the endpoints of paths search for optimal path
	std::vector<std::vector<node*>> paths;

	for (auto& p : endpoints) {

#if BFS_OR_DIJKSTRA

		// initialization
		node* source = p.first;
		node* target = p.second;
		// distance from source to node
		std::unordered_map<node*, int> dist;
		// previous node on the path from the source
		std::unordered_map<node*, node*> prev;

		std::queue<node*> q_next;

		for (node* n : nodes) {
			dist[n] = std::numeric_limits<int>::max(); // unknown
			prev[n] = nullptr; // unknown
		}

		dist[source] = 0;
		q_next.push(source);


		std::vector<node*> path;
		while (!q_next.empty() && path.empty()) {
			node* u = q_next.front();
			q_next.pop();

			// found path, construct it
			if (u == target) {
				// current node
				node* c = target;
				// while there is a previous node
				while (prev.at(c)) {
					path.insert(path.begin(), c);
					c = prev.at(c);
				}
				path.insert(path.begin(), c);
				continue;
			}

			for (size_t i = 0; i < u->edges.size(); i++) {
				auto e = u->edges[i];
				// neighbor
				node* v = e->vertex1 == u ? e->vertex2 : e->vertex1;

				if (dist[v] == std::numeric_limits<int>::max()) {
					dist[v] = dist[u] + 1;
					prev[v] = u;
					q_next.push(v);
				}
			}
		}
		paths.push_back(path);

#else
		// unvisited nodes
		std::unordered_set<node*> unvisited;
		// distance from source to node
		std::unordered_map<node*, int> dist;
		// previous node on the path from the source
		std::unordered_map<node*, node*> prev;
		node* source = p.first;
		node* target = p.second;

		// begin the actual algorithm
		for (node* n : nodes) {
			dist[n] = std::numeric_limits<int>::max(); // unknown
			prev[n] = nullptr; // unknown
			unvisited.insert(n);
		}

		dist[source] = 0;

		std::vector<node*> path;
		while (unvisited.size() != 0 && path.size() == 0) {
			// select node with minimum distance
			node* u = *std::min_element(
				unvisited.begin(),
				unvisited.end(),
				[&dist](node* const a, node* const b) {
				return dist[a] < dist[b];
			}
			);

			unvisited.erase(u);

			// found path, construct it
			if (u == target) {
				// current node
				node* c = target;
				// while there is a previous node
				while (prev.at(c)) {
					path.insert(path.begin(), c);
					c = prev.at(c);
				}
				path.insert(path.begin(), c);
			}

			// iterate over neighbors
			// for each doesn't work for some reason
			for (size_t i = 0; i < u->edges.size(); i++) {
				auto e = u->edges[i];
				// neighbor
				node* v = e->vertex1 == u ? e->vertex2 : e->vertex1;
				// alternative path
				auto alt = dist[u] + 1; // 1 because in this problem each edge is 1 long
										// better path?
				if (alt < dist[v]) {
					dist[v] = alt;
					prev[v] = u;
				}
			}
		}
		paths.push_back(path);
#endif	
	}

	// add pressure to each node
	for (auto& path : paths) {
		for (node* n : path) {
			n->pressure++;
		}
	}

	// find the maximum right side value in `pressure`
	node* max_pressure = *std::max_element(
		graph.nodes.begin(),
		graph.nodes.end(),
		[](node* const a, node* const b) {
			return a->pressure < b->pressure;
		}
	);

	// TODO DEBUG
	const static auto node_number = [&graph](node* n) -> int {
		return std::find(graph.nodes.begin(), graph.nodes.end(), n) - graph.nodes.begin() + 1;
	};

	std::cout << "time: " << (int)(((double)(clock() - begin) / CLOCKS_PER_SEC) * 1000) << "ms" << std::endl;
	std::cout << "# nodes: " << graph.nodes.size() << std::endl;
	std::cout << "# edges: " << graph.edges.size() << std::endl;
	std::cout << "# endpoints: " << endpoints.size() << std::endl;
	std::cout << "# paths: " << paths.size() << std::endl;
	std::cout
		<< "solution: node "
		<< node_number(max_pressure)
		<< ": "
		<< max_pressure->pressure
		<< std::endl;

	// print to output file
	std::ofstream of("maxflow.out", std::ios::trunc); // remove the contents of the file
	of << max_pressure->pressure << std::endl;
	of.close();

	return 0;
}

maxflow.in

5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4

maxflow.out

9