bigworld

compute diameter of flights graph
git clone https://a3nm.net/git/bigworld/
Log | Files | Refs

commit 075aeaf4300e905699433721e12a9cfdfc41608e
parent 622e52f0fab9193988909fc1bc0e7c827e24ea17
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue,  5 May 2015 23:37:40 +0200

new routes

Diffstat:
routes.c | 74+++++++++++++++++++++++++++++++++++++++++++++++++-------------------------
1 file changed, 49 insertions(+), 25 deletions(-)

diff --git a/routes.c b/routes.c @@ -1,54 +1,78 @@ #include <stdio.h> -#define NMAX 3500 +#define NMAX 10000 +#define AMAX 20000 #define INF 20000 +#define MULTI 20000 #define max(a, b) ((a)<(b) ? (b) : (a)) int d[NMAX][NMAX]; int nx[NMAX][NMAX]; -char code[NMAX][5]; +int airline[NMAX][NMAX]; +bool touchaf[NMAX][AMAX]; +bool touchat[NMAX][AMAX]; +bool touchf[NMAX]; +bool toucht[NMAX]; +char code[NMAX][10]; int main() { - int n, e, a, b; - scanf("%d", &n); - for (int i = 0; i < n; i++) - scanf("%s", (code[i])); - for (int i = 0; i < n; i++) - for (int j = 0; j < n; j++) { + while (1) { + int a; + scanf("%d", &a); + if (!a) + break; + scanf("%s", code[a]); + } + for (int i = 0; i < NMAX; i++) + for (int j = 0; j < NMAX; j++) { d[i][j] = (i == j) ? 0 : INF; nx[i][j] = -1; } - scanf("%d", &e); - for (int i = 0; i < e; i++) { - scanf("%d%d", &a, &b); - printf("read %s %s\n", code[a], code[b]); - if (a == b) - continue; - d[a][b] = d[b][a] = 1; - nx[a][b] = b; - nx[b][a] = a; + while (1) { + int a, f, t; + scanf("%d%d%d", &a, &f, &t); + if (!a) + break; + d[f][t] = 1; + touchaf[f][a] = true; + touchat[t][a] = true; + touchf[f] = true; + touchf[t] = true; + nx[f][t] = t; + airline[f][t] = airline[f][t] ? MULTI : a; + } + // transitive closure within each company on non-MULTI segments + for (int k = 0; k < NMAX; k++) { + printf ("%d of %d\n", k, NMAX); + for (int i = 0; i < NMAX; i++) + for (int j = 0; j < NMAX; j++) + if (d[i][k] == 1 && d[k][j] == 1 && airline[i][k] == airline[k][j] + && airline[i][k] != MULTI) { + d[i][j] = 1; + airline[i][j] = airline[i][k]; + } } - for (int k = 0; k < n; k++) { - printf ("%d of %d\n", k, n); - for (int i = 0; i < n; i++) - for (int j = 0; j < n; j++) + for (int k = 0; k < NMAX; k++) { + printf ("%d of %d\n", k, NMAX); + for (int i = 0; i < NMAX; i++) + for (int j = 0; j < NMAX; j++) if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; nx[i][j] = nx[i][k]; } } int best = 0; - for (int i = 0; i < n; i++) - for (int j = 0; j < n; j++) { + for (int i = 0; i < NMAX; i++) + for (int j = 0; j < NMAX; j++) { if (d[i][j] == INF) continue; best = max(d[i][j], best); if (d[i][j] == best) printf("%d: %s -> %s\n", best, code[i], code[j]); } - for (int i = 0; i < n; i++) - for (int j = 0; j < n; j++) + for (int i = 0; i < NMAX; i++) + for (int j = 0; j < NMAX; j++) if (d[i][j] == best) { printf("%d: %s -> %s: ", d[i][j], code[i], code[j]); printf("%s ", code[i]);