Cod sursa(job #202232)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 7 august 2008 00:27:54
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>

int n, m, p, x, y, a, b, c, d, viz[32005], ok, drum[32005], cost[32005];

typedef struct nod
{
	int x, c;
	nod *a;
} *pNod;
pNod v[32005];

int min(int x, int y){ return x < y ? x : y; }

void add(int x, int y, int c)
{
	pNod p;
	p = new nod;
	p -> x = y;
	p -> c = c;
	p -> a = v[x];
	v[x] = p;
}

void find(int nod, int dest, int vi)
{
	pNod p;
	viz[nod] = vi;
	for (p = v[nod]; p != NULL; p = p -> a)
	{
		if (!ok) return;
		if (viz[p -> x] != vi)
		{			
			if (p -> x == dest)
			{
				ok = 0;
				return;
			}
			drum[p -> x] = nod;
			cost[p -> x] = p -> c;
			find(p -> x, dest, vi);
		}
	}	
}

int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);

	int i, xn, yn, z;

	scanf("%d %d %d",&n,&m,&p);

	for (i = 1; i < n; i++)
	{
		scanf("%d %d",&x,&y);
		add(i+1,x,y);
		add(x,i+1,y);
	}

	scanf("%d %d %d %d %d %d",&x,&y,&a,&b,&c,&d);

	for (i = 1; i <= m; i++)
	{
		if (x == y) z = 0;
		else
		{
			ok = 1;
			z = 200000;
			drum[x] = 0;
			find(x, y, i);
			int t = y;
			while (drum[t])
			{
				z = min(z,cost[t]);
				t = drum[t];
			}

		}
		xn = (x * a + y * b) % n + 1;
		yn = (y * c + z * d) % n + 1;

		if (i > m - p) printf("%d\n",z);
		x = xn, y = yn;
	}

	return 0;
}