Cod sursa(job #1435555)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 13 mai 2015 19:29:49
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <string>
#include <cstdlib>
#include <utility>
#include <list>
#include <array>
#include <vector>
#include <queue>
using namespace std;

constexpr int inf = 1001;

class dial_pq {
	array<queue<int>, inf + 1> buf;
	int poz = 0;
	void clear() {
		while (buf[poz].empty()) {
			++poz;
		}
	}

public:
	void emplace(const int x, const int y) { buf[y].push(x); }
	const pair<int, int> top() {
		clear();
		return make_pair(buf[poz].front(), poz);
	}
	void pop() {
		clear();
		buf[poz].pop();
	}
};

int dial(const vector<list<pair<int, int> > > &vecini, const int x,
				 const int y) {

	dial_pq st;
	vector<int> rez(vecini.size(), inf);

	st.emplace(x, 0);
	rez[x] = 0;

	int cur = 0, cost_cur = 0, ipotetic = 0;

	while (true) {
		cur = st.top().first;
		cost_cur = st.top().second;
		st.pop();
		if (cur == y) {
			return rez[y];
		}
		if (rez[cur] == cost_cur) {
			for (const auto next : vecini[cur]) {
				ipotetic = max(next.second, cost_cur);
				if (ipotetic < rez[next.first]) {
					rez[next.first] = ipotetic;
					st.emplace(next.first, ipotetic);
				}
			}
		}
	}
}

void citeste_date(vector<list<pair<int, int> > > &vecini, int &x, int &y) {
	ifstream f("pscnv.in");
	int n, m;
	f >> n >> m >> x >> y >> ws;
	--x, --y;
	vecini.resize(n);
	string buf;
	buf.reserve(256);
	for (int i = 0, a, b, c; i < m; ++i) {
		getline(f, buf);
		char* poz = &buf[0];
		a = strtol(poz, &poz, 10);
		b = strtol(poz, &poz, 10);
		c = strtol(poz, &poz, 10);
		--a, --b;
		vecini[a].emplace_back(b, c);
	}
}

int main() {
	vector<list<pair<int, int> > > vecini;
	int x, y;
	citeste_date(vecini, x, y);
	ofstream g("pscnv.out");
	g << dial(vecini, x, y);
	return 0;
}