bigworld

commit 92b411360dd50c4769208cb7575820ba9ecbd5c0
parent 1711e513e7de9077685b6731493ffcbbadd2423f
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Wed, 20 May 2015 23:30:43 +0200

rename

Diffstat:
routes.cpp
 | 
100
-------------------------------------------------------------------------------
smallworld.cpp
 | 
100
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 100 insertions(+), 100 deletions(-)
diff --git a/routes.cpp b/routes.cpp
@@ -1,100 +0,0 @@
-#include <stdio.h>
-
-#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];
-int airline[NMAX][NMAX];
-//bool touchaf[NMAX][AMAX];
-//bool touchat[NMAX][AMAX];
-bool touchf[NMAX];
-bool toucht[NMAX];
-char code[NMAX][10];
-
-int main() {
-  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;
-    }
-  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;
-    toucht[t] = true;
-    nx[f][t] = t;
-    airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
-  }
-  int n = 0;
-  // transitive closure within each company on non-MULTI segments
-  for (int k = 0; k < NMAX; k++) {
-    if (!(touchf[k] && toucht[k]))
-      continue;
-    n++;
-    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][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k];
-          nx[i][j] = j;
-        }
-  }
-  int n2 = 0;
-  for (int k = 0; k < NMAX; k++) {
-    if (!(touchf[k] && toucht[k]))
-      continue;
-    n2++;
-    printf ("%d of %d\n", n2, n);
-    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 < 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 < 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]);
-        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;
-}
diff --git a/smallworld.cpp b/smallworld.cpp
@@ -0,0 +1,100 @@
+#include <stdio.h>
+
+#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];
+int airline[NMAX][NMAX];
+//bool touchaf[NMAX][AMAX];
+//bool touchat[NMAX][AMAX];
+bool touchf[NMAX];
+bool toucht[NMAX];
+char code[NMAX][10];
+
+int main() {
+  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;
+    }
+  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;
+    toucht[t] = true;
+    nx[f][t] = t;
+    airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a;
+  }
+  int n = 0;
+  // transitive closure within each company on non-MULTI segments
+  for (int k = 0; k < NMAX; k++) {
+    if (!(touchf[k] && toucht[k]))
+      continue;
+    n++;
+    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][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k];
+          nx[i][j] = j;
+        }
+  }
+  int n2 = 0;
+  for (int k = 0; k < NMAX; k++) {
+    if (!(touchf[k] && toucht[k]))
+      continue;
+    n2++;
+    printf ("%d of %d\n", n2, n);
+    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 < 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 < 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]);
+        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;
+}