bigworld.cpp (2959B)
1 #include <assert.h> 2 #include <cstdio> 3 #include <iostream> 4 #include <map> 5 #include <string> 6 #include <vector> 7 8 #define NMAX 3200 9 #define INF 20000 10 #define MULTI 200000 11 #define STEP 50 12 13 using namespace std; 14 15 int d[NMAX][NMAX]; 16 int nx[NMAX][NMAX]; 17 int airline[NMAX][NMAX]; 18 vector<string> code; 19 map<string, int> alias; 20 21 inline int regcode(string s) { 22 if (!alias.count(s)) { 23 alias[s] = code.size(); 24 code.push_back(s); 25 } 26 return alias[s]; 27 } 28 29 // if passed an argument, do the transitive closure 30 // algo is Floyd-Warshall with path reconstruction 31 // https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction 32 int main(int argc, char **argv) { 33 for (unsigned int i = 0; i < NMAX; i++) 34 for (unsigned int j = 0; j < NMAX; j++) { 35 d[i][j] = (i == j) ? 0 : INF; 36 nx[i][j] = -1; 37 } 38 while (1) { 39 int a; 40 int ret = scanf("%d", &a); 41 if (ret < 1) 42 break; 43 string fs, ts; 44 cin >> fs >> ts; 45 int f = regcode(fs), t = regcode(ts); 46 assert(f < NMAX && t < NMAX && a < MULTI); 47 assert(a != 0); 48 airline[f][t] = (airline[f][t] && airline[f][t] != a) ? MULTI : a; 49 d[f][t] = 1; 50 nx[f][t] = t; 51 } 52 unsigned int n = code.size(); 53 if (argc >= 2) { 54 // transitive closure within each company on non-MULTI segments 55 for (unsigned int k = 0; k < n; k++) { 56 if (!(k % STEP)) 57 fprintf(stderr, "closing: %d of %d\n", k, n); 58 for (unsigned int i = 0; i < n; i++) 59 for (unsigned int j = 0; j < n; j++) 60 // if both have edges with same non-multi airline then close 61 if (d[i][k] == 1 && d[k][j] == 1 && airline[i][k] == airline[k][j] 62 && airline[i][k] != MULTI) { 63 d[i][j] = 1; 64 // add airline to new edge, can make it MULTI 65 airline[i][j] = (airline[i][j] && airline[i][j] != airline[i][k]) ? MULTI : airline[i][k]; 66 nx[i][j] = j; 67 } 68 } 69 } 70 for (unsigned int k = 0; k < n; k++) { 71 if (!(k % STEP)) 72 fprintf(stderr, "computing: %d of %d\n", k, n); 73 for (unsigned int i = 0; i < n; i++) 74 for (unsigned int j = 0; j < n; j++) 75 if (d[i][j] > d[i][k] + d[k][j]) { 76 d[i][j] = d[i][k] + d[k][j]; 77 nx[i][j] = nx[i][k]; 78 } 79 } 80 int best = 0; 81 for (unsigned int i = 0; i < n; i++) 82 for (unsigned int j = 0; j < n; j++) { 83 if (d[i][j] == INF) 84 continue; 85 best = max(d[i][j], best); 86 /* if (d[i][j] == best) 87 printf("%d: %s -> %s\n", best, code[i].c_str(), code[j].c_str()); */ 88 } 89 for (unsigned int i = 0; i < n; i++) 90 for (unsigned int j = 0; j < n; j++) 91 if (d[i][j] == best) { 92 printf("%d: %s -> %s: ", d[i][j], code[i].c_str(), code[j].c_str()); 93 printf("%s ", code[i].c_str()); 94 int u = i, v = j; 95 while (u != v) { 96 assert(u >= 0); 97 u = nx[u][v]; 98 printf("%s ", code[u].c_str()); 99 } 100 printf("\n"); 101 } 102 return 0; 103 } 104