#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define EDGE_PROB 0.2
#define PLUS_INFTY 1000000000

typedef struct {
   int n;
   char **type;
   int **cost;
} graph;

graph gengraph ( int n )
{
   graph G;
   int i, j;

   printf("%d\n", n);

   G.n = n;
   G.type = (char **)malloc(n * sizeof(char *));
   G.cost = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      G.type[i] = (char *)malloc(n * sizeof(char));
      for (j=0; j<n; ++j) G.type[i][j] = '-';
      G.cost[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) G.cost[i][j] = PLUS_INFTY;
   }

   for (i=0; i<n; ++i) {
      for (j=0; j<n; ++j) {
         if ((i != j) && ((double)rand() / (double)RAND_MAX <= EDGE_PROB)) {
            G.type[i][j] = (rand() % 2) ? 'a' : 'n';
            G.cost[i][j] = 1000 + rand() % 9000;
            printf("%-3d %-3d %-5d %c\n", i, j, G.cost[i][j], G.type[i][j]);
         } else if (i == j) {
            G.type[i][j] = 's';
            G.cost[i][j] = 0;
         }
      }
   }
   printf("-1\n");

   return G;
}

void prngraph ( graph G )
{
   int i, j;

   for (i=0; i<G.n; ++i) {
      printf("    %-3d ->", i);
      for (j=0; j<G.n; ++j) {
         if ((G.type[i][j] == 'a') || (G.type[i][j] == 'n'))  {
            printf(" %3d (%4d, %c)", j, G.cost[i][j], G.type[i][j]);
         }
      }
      printf("\n");
   }
}

graph getAIgraph ( graph G )
{
   graph H;
   int n, i, j;

   n = H.n = G.n;

   H.type = (char **)malloc(n * sizeof(char *));
   H.cost = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      H.type[i] = (char *)malloc(n * sizeof(char));
      for (j=0; j<n; ++j) H.type[i][j] = '-';
      H.cost[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) H.cost[i][j] = PLUS_INFTY;
   }

   for (i=0; i<n; ++i) {
      for (j=0; j<n; ++j) {
         if (G.type[i][j] == 'a') {
            H.type[i][j] = 'a';
            H.cost[i][j] = G.cost[i][j];
         } else if (i == j) {
            H.type[i][j] = 's';
            H.cost[i][j] = 0;
         }
      }
   }

   return H;
}

int **APSP ( graph G )
{
   int n, i, j, k, c;
   int **C;

   n = G.n;
   C = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      C[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) C[i][j] = G.cost[i][j];
   }

   for (k=0; k<n; ++k) {
      for (i=0; i<n; ++i) {
         for (j=0; j<n; ++j) {
            c = C[i][k] + C[k][j];
            if (c < C[i][j]) C[i][j] = c;
         }
      }
   }

   return C;
}

int **APSP1 ( graph G, int **C )
{
   int n, i, j, k, l, d;
   int **D;

   n = G.n;
   D = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      D[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j) D[i][j] = C[i][j];
   }

   for (i=0; i<n; ++i) {
      for (j=0; j<n; ++j) {
         if (D[i][j] == PLUS_INFTY) {
            for (k=0; k<n; ++k) {
               if (C[i][k] < PLUS_INFTY) {
                  for (l=0; l<n; ++l) {
                     if (C[l][j] < PLUS_INFTY) {
                        d = C[i][k] + G.cost[k][l] + C[l][j];
                        if (d < D[i][j]) D[i][j] = d;
                     }
                  }
               }
            }
         }
      }
   }

   return D;
}

int **APSPany ( graph G, int **C1 )
{
   int n, i, j, **C, **D;

   C = APSP(G);
   n = G.n;
   D = (int **)malloc(n * sizeof(int *));
   for (i=0; i<n; ++i) {
      D[i] = (int *)malloc(n * sizeof(int));
      for (j=0; j<n; ++j)
         D[i][j] = (C1[i][j] < PLUS_INFTY) ? C1[i][j] : C[i][j];
      free(C[i]);
   }
   free(C);
   return D;
}

void prncosts ( int **C, int n )
{
   int i, j;

   printf("          ");
   for (j=0; j<n; ++j) printf(" %5d", j);
   printf("\n\n");

   for (i=0; i<n; ++i) {
      printf("    %-3d ->", i);
      for (j=0; j<n; ++j) {
         if (C[i][j] < PLUS_INFTY) printf(" %5d", C[i][j]);
         else printf("     -");
      }
      printf("\n");
   }
}

int main ( int argc, char *argv[] )
{
   int n;
   graph G, H;
   int **C1, **C2, **C3;

   srand((unsigned int)time(NULL));
   n = (argc > 1) ? atoi(argv[1]) : 20;

   G = gengraph(n);
   printf("\n+++ Original graph\n");
   prngraph(G);

   H = getAIgraph(G);
   printf("\n+++ AI subgraph\n");
   prngraph(H);

   C1 = APSP(H);
   printf("\n+++ Cheapest AI prices\n");
   prncosts(C1,n);

   C2 = APSP1(G,C1);
   printf("\n+++ Cheapest prices with at most one non-AI leg\n");
   prncosts(C2,n);

   C3 = APSPany(G,C1);
   printf("\n+++ Cheapest prices with any number of non-AI legs\n");
   prncosts(C3,n);

   exit(0);
}