Cod sursa(job #831560)

Utilizator moscaliuc_ovidiuMoscaliuc Ovidiu moscaliuc_ovidiu Data 8 decembrie 2012 19:06:17
Problema Radiatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <set>
#include <vector>
#include <stack>

#define MAX_N ((const unsigned int)15100)

class Edge
{
public:
	int x;
	int y;
	int cost;

public:
	Edge(int _x, int _y, int _cost) :
		x(_x), y(_y), cost(_cost)
	{
	}

	bool operator < (const Edge &_other) const
	{
		return this->cost < _other.cost;
	}
};

class Pair
{
public:
	int node;
	int cost;

public:
	Pair(int _node, int _cost) :
		node(_node), cost(_cost)
	{
	}

	bool operator < (const Pair &_other) const
	{
		return this->cost < _other.cost;
	}
};

typedef std::multiset<Edge>		Edges;
typedef std::set<int>			NodeSet;
typedef std::multiset<Pair>		Neighbours;

Neighbours Graf[MAX_N];
bool visited[MAX_N];
Edges edges;
NodeSet inserted;

int compute(int _current, int _dest)
{
	typedef std::stack<Pair>	NodeStack;

	NodeStack stack;
	int cost = 0;
	bool bFound = false;

	visited[_current] = true;
	stack.push(Pair(_current, cost));

	while(stack.size())
	{
		Neighbours::iterator itNeighbour;

		Pair current = stack.top();

		bool bGoDeep = false;

		for (itNeighbour = Graf[current.node].begin(); Graf[current.node].end() != itNeighbour && !bFound; ++ itNeighbour)
		{
			if (!visited[itNeighbour->node])
			{
				bGoDeep = true;
				visited[current.node] = true;

				stack.push(Pair(itNeighbour->node, current.cost > itNeighbour->cost ? current.cost : itNeighbour->cost));

				if (itNeighbour->node == _dest)
				{
					bFound = true;

					if (stack.top().cost > cost)
						cost = stack.top().cost;
				}
			}
		}

		if (!bGoDeep)
		{
			visited[current.node] = false;
			stack.pop();
		}
	}

	return cost;
}

int main()
{
	std::ifstream fin("radiatie.in");
	std::ofstream fout("radiatie.out");

	int N, M, K;
	int x, y;
	
	unsigned int c;

	fin>>N>>M>>K;

	for (int i = 0; i < M; ++ i)
	{
		fin>>x>>y>>c;

		edges.insert(Edge(x, y, c));
	}

	inserted.insert(1);

	while(inserted.size() != N)
	{
		Edges::iterator	itEdge;

		for (itEdge = edges.begin(); edges.end() != itEdge && inserted.find(itEdge->x) == inserted.end(); ++ itEdge);

		if (edges.end() == itEdge)
			break;

		Edge edge = *itEdge;

		Graf[edge.x].insert(Pair(edge.y, edge.cost));
		Graf[edge.y].insert(Pair(edge.x, edge.cost));

		inserted.insert(itEdge->y);
		edges.erase(itEdge);
	}

	for (int i = 0; i < K; ++ i)
	{
		fin>>x>>y;
		fout<<compute(x, y)<<'\n';
	}

	fin.close();
	fout.close();

	return 0;
}