bigworld

commit 622e52f0fab9193988909fc1bc0e7c827e24ea17
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue,  5 May 2015 23:34:06 +0200

first version

Diffstat:
routes.c
 | 
67
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 67 insertions(+), 0 deletions(-)
diff --git a/routes.c b/routes.c
@@ -0,0 +1,67 @@
+#include <stdio.h>
+
+#define NMAX 3500
+#define INF 20000
+
+#define max(a, b) ((a)<(b) ? (b) : (a))
+
+int d[NMAX][NMAX];
+int nx[NMAX][NMAX];
+char code[NMAX][5];
+
+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++) {
+      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;
+  }
+  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++)
+        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++) {
+      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++)
+      if (d[i][j] == best) {
+        printf("%d: %s -> %s: ", d[i][j], code[i], code[j]);
+        printf("%s ", code[i]);
+        int u = i, v = j;
+        while (u != v) {
+          if (u < 0) {
+            printf("stuck!");
+            break;
+          }
+          u = nx[u][v];
+          printf("%s ", code[u]);
+        }
+        printf("\n");
+      }
+  return 0;
+}