Cod sursa(job #411)

Utilizator wefgefAndrei Grigorean wefgef Data 11 decembrie 2006 10:53:22
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define pb(v, a) v.push_back(a)
#define sz(a) a.size()
#define sch(x, y) x ^= y ^= x ^= y

#define Nmax 250005

int n, start, stop, heap[Nmax], poz[Nmax], el[Nmax], viz[Nmax], lung;
vector< vector<int> > vec, c;

void readdata()
{
	freopen("pscnv.in", "r", stdin);
	freopen("pscnv.out", "w", stdout);
	
	int m, i, a, b, cost;
	
	scanf("%d %d %d %d", &n, &m, &start, &stop);
	vec.resize(n+1);
	c.resize(n+1);
	
	for (i = 0; i < m; ++i)
	{
		scanf("%d %d %d", &a, &b, &cost);
		pb(vec[a], b);
		pb(c[a], cost);
	}
}

void inline recon(int k)
{
	int max = k;
	
	if (2*k <= lung)
	if (heap[2*k] < heap[max]) max = 2*k;
	
	if (2*k+1 <= lung)
	if (heap[2*k+1] < heap[max]) max = 2*k+1;	
	
	if (max > k)
	{
		sch(heap[max], heap[k]);
		sch(el[max], el[k]);
		poz[el[max]] = max; poz[el[k]] = k;
		recon(max);
	}
}

void inline scoate()
{
	heap[1] = heap[lung];
	el[1] = el[lung];
	poz[el[1]] = 1;
	--lung;
	recon(1);
}

void inline recon2(int k)
{
	if (k < 2) return;
	
	int max = k/2;
	if (heap[max] > heap[k])
	{
		sch(heap[max], heap[k]);
		sch(el[max], el[k]);
		poz[el[k]] = k; poz[el[max]] = max;
		recon2(max);
	}
}

void solve()
{
	int i, nod, lim, d;
	
	lung = 1;
	heap[lung] = 0;
	el[lung] = start;
	poz[start] = 1;
	while (!viz[stop])
	{
		nod = el[1];
		d = heap[1];
		scoate();
		viz[nod] = 1;
		
		lim = sz(vec[nod]);
		for (i = 0; i < lim; ++i)
		if (!viz[vec[nod][i]])
			if (poz[vec[nod][i]] == 0)
			{
				heap[++lung] = max(d, c[nod][i]);
				el[lung] = vec[nod][i];
				poz[el[lung]] = lung;
				recon2(lung);
			}
			else
			{
				if (max(d, c[nod][i]) < heap[poz[vec[nod][i]]])
				{
					heap[poz[vec[nod][i]]] = max(d, c[nod][i]);
					recon2(poz[vec[nod][i]]);
				}
			}
	}
	printf("%d\n", d);
}

int main()
{
	readdata();
	solve();
	return 0;
}