Cod sursa(job #412868)

Utilizator GulyanAlexandru Gulyan Data 6 martie 2010 20:08:05
Problema Subsir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
// bile7.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>

#define GOL 0
#define ALBASTRA 1
#define ROSIE 2

#define INF 30000

struct nod {
	int rad;
	int *fii;
	int nf;
	char bila;
};

//date globale
int n, p, k;
nod *v;

/*
int min(int a, int b) {
	if(a >= INF && b >= INF)
		return INF;
	return a > b ? (a > INF ? INF : a) : (b > INF ? INF : b);
}
*/

int in_path(int i) {
	int j = p;
	do {
		if(j == i)
			return 1;
		j = v[j].rad;
	}while(j != 0);
	return 0;
}

int elib_nod(int i, int *e) {
	if(v[i].bila == ALBASTRA)
		return INF;
	if(v[i].bila == GOL && !in_path(i)) {
		*e = i;
		return 0;
	}
	int c = INF;
	int cc, cbn;//cost curent, curent best node
	for(int j = 0; j < v[i].nf; ++j) {
		cc = elib_nod(v[i].fii[j], &cbn);
		//printf("cc[%d]=%d\n", v[i].fii[j], cc);
		if( c > 1 + cc ) {
			c = 1 + cc;
			*e = cbn;
		}
	}
	//printf("e=%d\n", *e);
	return c;
}

int main()
{
	FILE *f1 = fopen("bile7.in", "r");
	FILE *f2 = fopen("bile7.out", "w");
	int i, j;

	fscanf(f1, "%d%d%d", &n, &p, &k);

	//initializare
	v = (nod*)(malloc(sizeof(nod) * (1 + n)));
	for(i = 0; i <= n; ++i) {
		v[i].bila = GOL;
		v[i].rad = 0;
	}

	//citirea datelor
	for(i = 1; i <= n; ++i) {
		fscanf(f1, "%d", &(v[i].nf));
		if(v[i].nf == 0)
			continue;
		v[i].fii = (int *)malloc(sizeof(int) * v[i].nf);
		for(j = 0; j < v[i].nf; ++j) {
			fscanf(f1, "%d", v[i].fii + j);
			v[v[i].fii[j]].rad = i;
		}
	}

	//pozitionarea bilelor
	v[p].bila = ALBASTRA;
	for(i = 0; i < k; ++i) {
		fscanf(f1, "%d", &j);
		v[j].bila = ROSIE;
	}

	//TODO
	int c = 0, cc;
	i = p;
	do{
		i = v[i].rad;
		if(v[i].bila != ROSIE)
			continue;
		cc = elib_nod(i, &j);
		c += cc;
		v[j].bila = v[i].bila;
		v[i].bila = GOL;
	}while(i != 0);

	fprintf(f2, "%d\n", c);
	

	//eliberare memorie
	for(i = 0; i < n; ++i)
		if(v[i].nf > 0)
			free(v[i].fii);
	free(v);

	//getch();

	fclose(f1);
	fclose(f2);

	return 0;
}