Cod sursa(job #1337)

Utilizator pantaniMarco Pantani pantani Data 13 decembrie 2006 13:06:01
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdlib.h>

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
#define Mmax 500005

int n, start, stop, heap[Nmax], poz[Nmax], el[Nmax], viz[Nmax], lung, *G[Nmax], *G2[Nmax], gr[Nmax];
int m1[Mmax], m2[Mmax], m3[Mmax];
vector< vector<int> > vec, c;

void readdata()
{
	freopen("pscnv.in", "r", stdin);
	freopen("pscnv.out", "w", stdout);
	
	int m, i, a, b, cost, poz;
	char s[20];
	
	scanf("%d %d %d %d", &n, &m, &start, &stop);
	vec.resize(n+1);
	c.resize(n+1);
	
	for (i = 1; i <= m; ++i)
	{
/*		
		gets(s);
		lung = strlen(s);
		scanf("\n");
		a = 0; b = 0; cost = 0;
		poz = 0;
		while (s[poz] != ' ')
			a = a*10+s[poz++]-'0';
		++poz;
		while (s[poz] != ' ')
			b = b*10+s[poz++]-'0';
		poz++;
		while (poz < lung)
			cost = cost*10+s[poz++]-'0';
*/
			
		scanf("%d %d %d", &a, &b, &cost);
//		pb(vec[a], b);
//		pb(c[a], cost);
		m1[i] = a; m2[i] = b; m3[i] = cost;
		++gr[a];
	}
	
	for (i = 1; i <= n; ++i)
	{
		G[i] = (int *)malloc((gr[i]+1) * sizeof(int));
		G[i][gr[i]] = -1;
		G2[i] = (int *)malloc((gr[i]+1) * sizeof(int));
		G2[i][gr[i]] = -1;
		gr[i] = 0;
	}
	for (i = 1; i <= m; ++i)
	{
		G[m1[i]][ gr[ m1[i] ] ] = m2[i];
		G2[m1[i]][ gr[ m1[i] ]++ ] = m3[i];
	}
}

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, *p, *p2;
	
	lung = 1;
	heap[lung] = 0;
	el[lung] = start;
	poz[start] = 1;
	while (!viz[stop])
	{
		nod = el[1];
		d = heap[1];
		scoate();
		viz[nod] = 1;
		
		for (p = G[nod], p2 = G2[nod]; *p != -1; ++p, ++p2)
		if (!viz[*p])
			if (poz[*p] == 0)
			{
				heap[++lung] = max(d, *p2);
				el[lung] = *p;
				poz[el[lung]] = lung;
				recon2(lung);
			}
			else
			{
				if (max(d, *p2) < heap[poz[*p]])
				{
					heap[poz[*p]] = max(d, *p2);
					recon2(poz[*p]);
				}
			}
	}
	printf("%d\n", d);
}

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