#include //#include unsigned char distance[201][201]; int regions; int towns; int people; int persontown[31]; int huge personregion[31][251]; int huge persondistance[31][251]; unsigned char huge regionindex[251][251]; void printdistances (ofstream &output) { int i,j; for (i = 0; i < regions; i++) { for (j = 0; j < regions; j++) { output.width(4); output << int(distance[i][j]); } output << "\n"; } output << "\n"; } void printpeople (ofstream &output, int zuh = 3) { int i, j; for (i = 0; i < people; i++) { if (zuh & 1) { for (j = 0; j < regions; j++) if (personregion[i][j]) output << " YES"; else output << " NO"; output << "\n"; } if (zuh & 2) { for (j = 0; j < regions; j++) { output.width(4); output << int(persondistance[i][j]); } output << "\n"; } } } void connection(int a, int b, int r) { if (a < b) { int c = a; a = b; b = c; } if (regionindex[a][b] == 255) { regionindex[a][b] = r; return; } else { distance[r][regionindex[a][b]] = 1; distance[regionindex[a][b]][r] = 1; } } int main() { // long s = clock(); int i, j, k; ifstream input; ofstream output; input.open ("walls.in"); output.open ("walls.out"); input >> regions; input >> towns; input >> people; for (i = 0; i < people; i++) { input >> persontown[i]; persontown[i]--; } for (i = 0; i < people; i++) for (j = 0; j < towns; j++) personregion[i][j] = 0; for (i = 0; i < towns; i++) for (j = 0; j < towns; j++) regionindex[i][j] = 255; for (i = 0; i < regions; i++) for (j = 0; j < regions; j++) if (i != j) distance[i][j] = 255; else distance[i][j] = 0; for (i = 0; i < regions; i++) { int vertices; input >> vertices; int first, lag, current; for (j = 0; j < vertices; j++) { input >> current; current--; for (k = 0; k < people; k++) if (persontown[k] == current) personregion[k][i] = 1; if (j != 0) connection(current, lag, i); else first = current; lag = current; if (j == vertices-1 && j > 0) connection(current, first, i); } } for (k = 0; k < regions; k++) for (i = 0; i < regions; i++) for (j = 0; j < regions; j++) { int p = distance[i][k]; int q = distance[k][j]; int r = distance[i][j]; if (p + q < r) distance[i][j] = p+q; } for (i = 0; i < people; i++) for (j = 0; j < regions; j++) { int best = 10000; for (k = 0; k < regions; k++) if (personregion[i][k] && distance[k][j] < best) best = distance[k][j]; persondistance[i][j] = best; } int bestregion; long best = 1000000l; for (i = 0; i < regions; i++) { long cur = 0; for (j = 0; j < people; j++) cur += persondistance[j][i]; if (cur < best) { best = cur; bestregion = i; } } output << best << "\n"; output << (bestregion+1) << "\n"; // long e = clock(); // cout << (e-s)/CLK_TCK << "\n"; input.close (); output.close (); return 0; }