Cod sursa(job #1435218)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 12 mai 2015 14:41:05
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <utility>
#include <vector>
#include <array>
#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<vector<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<vector<pair<int, int> > >& vecini, int& x, int& y){
	ifstream f("pscnv.in");
	int n, m;
	f >> n >> m >> x >> y;
	--x, --y;
	vecini.resize(n);
	for(int i = 0, a, b, c; i < m; ++i){
		f >> a >> b >> c;
		--a, --b;
		vecini[a].emplace_back(b, c); } }

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