Pagini recente » Cod sursa (job #2181053) | Cod sursa (job #56783) | Cod sursa (job #2280676) | Cod sursa (job #2760876) | Cod sursa (job #412868)
Cod sursa(job #412868)
// 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;
}