#define N 100000 #define MD 100000000 int abs_(int a) { return a > 0 ? a : -a; } int ej[N][4], eo[N]; int bfs(int n, int s) { static int dd[N], qu[N]; int i, head, cnt, sum; for (i = 0; i < n; i++) dd[i] = n; head = cnt = 0; dd[s] = 0, qu[head + cnt++] = s; while (cnt) { int d, o; i = qu[cnt--, head++], d = dd[i] + 1; for (o = eo[i]; o--; ) { int j = ej[i][o]; if (dd[j] > d) dd[j] = d, qu[head + cnt++] = j; } } sum = 0; for (i = s + 1; i < n; i++) sum = (sum + dd[i]) % MD; return sum; } int DistanceSum(int n, int *xx, int *yy) { int i, j, sum; for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (abs_(xx[i] - xx[j]) + abs_(yy[i] - yy[j]) == 1) ej[i][eo[i]++] = j; sum = 0; for (i = 0; i < n; i++) sum = (sum + bfs(n, i)) % MD; return sum; }