commit 3d27d28fcd419316e817b7d2e0675769c5cc9e7a
parent 075aeaf4300e905699433721e12a9cfdfc41608e
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 6 May 2015 02:41:44 +0200
continue
Diffstat:
| routes.c | | | 91 | ------------------------------------------------------------------------------- |
| routes.cpp | | | 100 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| routes.py | | | 49 | +++++++++++++++++++++++++++++++++++++++++++++++++ |
| script.sh | | | 3 | +++ |
4 files changed, 152 insertions(+), 91 deletions(-)
diff --git a/routes.c b/routes.c
@@ -1,91 +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;
- 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 < 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 < 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/routes.cpp b/routes.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;
+}
diff --git a/routes.py b/routes.py
@@ -0,0 +1,49 @@
+#!/usr/bin/python
+
+import sys
+
+E = {}
+
+best = 1
+
+for l in sys.stdin.readlines():
+ v = l.split(',')
+ f = v[2]
+ t = v[4]
+ if f not in E.keys():
+ E[f] = set()
+ E[f].add(t)
+ # symmetrize
+ if t not in E.keys():
+ E[t] = set()
+ E[t].add(f)
+
+print (len(E.keys()))
+l = sorted(list(E.keys()))
+rev = {}
+for i in range(len(l)):
+ print (l[i])
+ rev[l[i]] = i
+ne = sum(len(E[x]) for x in l)
+print (ne)
+for i in range(len(l)):
+ for x in E[l[i]]:
+ print("%d %d" % (i, rev[x]))
+
+#print ("airports: %d" % len(E.keys()))
+#
+#for a0 in E.keys():
+# q = [(a0, 0)]
+# seen = set()
+# while len(q) > 0:
+# a, d = q[0]
+# q = q[1:]
+# if a in seen:
+# continue
+# seen.add(a)
+# best = max(d, best)
+# if d == best:
+# print ("%d: %s -> %s" % (d, a0, a))
+# for b in E[a]:
+# q.append((b, d+1))
+#
diff --git a/script.sh b/script.sh
@@ -0,0 +1,3 @@
+cut -d, -f1,5,6 airports.dat | sed 's/""/"***"/g;s/\\N/"****"/g;s/,/ /;s/,/-/' | tr -d '"'
+cut -d, -f2,4,6,7 routes.dat | grep -v Y | tr ',' ' ' | grep -v '\\N' | sort -k1,1n | sed 's/^5399 /11838 /g' > edges
+cat nodes <(echo 0) edges <(echo 0 0 0) > input
