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

#define EDGE_PROBABILITY 0.05
#define INFINITY 1000000000
#define UNDEFINED -1

typedef struct _node {
   int nbr;
   struct _node *next;
} node;

typedef struct {
   int n;
   int m;
   int *vwt;
   node **adjlist;
} graph;

void findclose ( graph G, int *C, int d, int *P, int k )
{
   node *p;

   C[P[k]] = 1;
   if (k == d) return;
   p = G.adjlist[P[k]];
   while (p) {
      P[k+1] = p -> nbr;
      findclose(G,C,d,P,k+1);
      p = p -> next;
   }
}

void getst ( graph G, int n, int *s, int *t )
{
   int i, j, k, N, d, *C, *P;

   N = G.n;
   C = (int *)malloc(N * sizeof(int));
   P = (int *)malloc(10 * sizeof(int));

   d = 4;
   for (i=0; i<n; ++i) {
      for (j=0; j<n; ++j) {
         for (k=0; k<N; ++k) C[k] = 0;
         P[0] = i*n+j;
         findclose(G,C,d,P,0);
         if (C[j*n+i] == 0) {
            *s = i; *t = j;
            free(C); free(P);
            return;
         }
      }
   }

   i = j = UNDEFINED;
   while (i == j) {
      i = rand() % n; j = rand() % n;
   }
   *s = i; *t = j;
   free(C); free(P);
}

void addundirectededge ( graph G, int u, int v, int *m )
{
   node *p;

   if (*m % 10 == 0) printf("\n   ");
   printf(" (%2d,%2d)", u, v);
   ++(*m);

   p = (node *)malloc(sizeof(node));
   p -> nbr = v;
   p -> next = G.adjlist[u];
   G.adjlist[u] = p;

   p = (node *)malloc(sizeof(node));
   p -> nbr = u;
   p -> next = G.adjlist[v];
   G.adjlist[v] = p;
}

graph geninput ( int n )
{
   graph G;
   int u, v, m;
   node *p;

   G.n = n;
   G.vwt = (int *)malloc(n * sizeof(int));
   G.adjlist = (node **)malloc(n * sizeof(node *));

   printf("+++ Path lengths:");
   for (u=0; u<n; ++u) {
      if (rand() % 2) G.vwt[u] = 1; else G.vwt[u] = 2 + rand() % 2;
      G.adjlist[u] = NULL;
      printf(" %d", G.vwt[u]);
   }
   printf("\n+++ Edges:");

   m = 0;
   for (v=n-1; v>=1; --v) addundirectededge(G, rand() % v, v, &m);
   for (v=1; v<n; ++v) {
      for (u=v-1; u>=0; --u) {
         if (((double)rand() / (double)RAND_MAX) < EDGE_PROBABILITY) {
            p = G.adjlist[u];
            while (p) {
               if (p -> nbr == v) break;
               p = p -> next;
            }
            if (p == NULL) addundirectededge(G,u,v,&m);
         }
      }
   }
   printf("\n");

   G.m = m;
   return G;
}

void prngraph ( graph G )
{
   int u;
   node *p;

   printf("    Number of vertices: %d\n", G.n);
   printf("    Number of edges   : %d\n", G.m);
   for (u=0; u<G.n; ++u) {
      printf("    %-3d (%d) -> ", u, G.vwt[u]);
      p = G.adjlist[u];
      while (p) {
         printf("%3d", p -> nbr);
         p = p -> next;
         if (p) printf(",");
      }
      printf("\n");
   }
}

void addedge ( graph R, int u, int v )
{
   node *p;

   p = (node *)malloc(sizeof(node));
   p -> nbr = v;
   p -> next = R.adjlist[u];
   R.adjlist[u] = p;
}

void findreach ( int *U, graph G, int *P, int l, int k )
{
   int u, v, i;
   node *p;

   if (k == l) {
      U[P[k]] = 1;
      return;
   }
   u = P[k];
   p = G.adjlist[u];
   while (p) {
      v = p -> nbr;
      for (i=0; i<=k; ++i) if (P[i] == v) break;
      if (i == k+1) {
         P[i] = v;
         findreach(U,G,P,l,i);
      }
      p = p -> next;
   }
}

graph genrgraph ( graph G )
{
   graph R;
   int u, v, l, *U, *P;

   R.n = G.n;
   R.m = 0;
   R.vwt = (int *)malloc(R.n * sizeof(int));
   R.adjlist = (node **)malloc(R.n * sizeof(node));
   for (u=0; u<R.n; ++u) {
      R.adjlist[u] = NULL;
      R.vwt[u] = G.vwt[u];
   }

   U = (int *)malloc(R.n * sizeof(int));
   P = (int *)malloc(R.n * sizeof(int));
   for (u=0; u<R.n; ++u) {
      for (v=0; v<R.n; ++v) U[v] = 0;
      P[0] = u; l = R.vwt[u];
      findreach(U,G,P,l,0);
      for (v=R.n-1; v>=0; --v) {
         if (U[v]) {
            addedge(R,u,v);
            ++(R.m);
         }
      }
   }

   free(U); free(P);
   return R;
}

graph gensrgraph ( graph R )
{
   graph S;
   int n, u, v, x, y;
   node *p, *q;

   n = R.n;
   S.n = n * n;
   S.m = 0;
   S.vwt = (int *)malloc(n * n * sizeof(int));
   S.adjlist = (node **)malloc(n * n * sizeof(node *));
   for (u=0; u<n*n; ++u) S.adjlist[u] = NULL;
   for (u=0; u<n; ++u) {
      for (v=0; v<n; ++v) {
         S.vwt[n*u+v] = R.vwt[u] + R.vwt[v];
         p = R.adjlist[u];
         while (p) {
            x = p -> nbr;
            q = R.adjlist[v];
            while (q) {
               y = q -> nbr;
               addedge(S,n*u+v,n*x+y);
               ++S.m;
               q = q -> next;
            }
            p = p -> next;
         }
      }
   }
   return S;
}

void showsoln ( graph G, int n, int s, int t, int *prev, int *nsteps, int *cost )
{
   if (s != t) {
      ++(*nsteps);
      *cost += G.vwt[prev[t]];
      showsoln(G,n,s,prev[t],prev,nsteps,cost);
   }
   printf(" (%d,%d)", t / n, t % n);
}

void BFS ( graph S, int n, int s, int t, int noshare )
{
   int *visited, l, nsteps, cost, *prev;
   int *Q, *L, F, B;
   int src, tgt, tgtfound, u, v;
   node *p;

   prev = (int *)malloc(n * n * sizeof(int));
   visited = (int *)malloc(n * n * sizeof(int));
   for (u=0; u<n*n; ++u) { prev[u] = UNDEFINED; visited[u] = 0; }
   if (noshare) for (u=0; u<n; ++u) visited[n*u+u] = 1;

   src = n*s+t; tgt = n*t+s;

   Q = (int *)malloc(n * n * sizeof(int));
   L = (int *)malloc(n * n * sizeof(int));
   Q[0] = src; L[0] = 0; visited[src] = 1;
   F = B = 0; tgtfound = 0;
   while (F <= B) {
      u = Q[F]; l = L[F]; ++F;
      if (u == tgt) { tgtfound = 1; break; }
      p = S.adjlist[u];
      while (p) {
         v = p -> nbr;
         if (!visited[v]) {
            ++B;
            Q[B] = v;
            L[B] = l+1;
            visited[v] = 1;
            prev[v] = u;
         }
         p = p -> next;
      }
   }

   if (!tgtfound) {
      printf("    The puzzle is not solvable\n");
   } else {
      printf("    Steps:"); nsteps = cost = 0;
      showsoln(S,n,s*n+t,t*n+s,prev,&nsteps,&cost); printf("\n");
      printf("    Number of steps = %d\n", nsteps);
      printf("    Total effort    = %d\n", cost);
   }

   free(Q); free(L); free(visited); free(prev);
}

void heapify ( int *H, int *V, int i, int *I )
{
   int n, l, r, m, t;

   n = H[0];
   while (1) {
      l = 2*i; if (l > n) break;
      r = 2*i+1; if (r > n) m = l; else m = (H[l] <= H[r]) ? l : r;
      if (H[i]<H[m]) break;
      t = H[i]; H[i] = H[m]; H[m] = t;
      t = V[i]; V[i] = V[m]; V[m] = t;
      I[V[i]] = i; I[V[m]] = m;
      i = m;
   }
}

void makeheap ( int *H, int *V, int *I )
{
   int i;

   for (i=H[0]/2; i>=1; --i) heapify(H,V,i,I);
}

void delmin ( int *H, int *V, int *I )
{
   int n;

   n = H[0]; if (n <= 0) return;
   I[V[1]] = UNDEFINED;
   I[V[n]] = 1;
   H[1] = H[n];
   V[1] = V[n];
   --(H[0]);
   heapify(H,V,1,I);
}

void reducedist ( int *H, int *V, int j, int d, int *I )
{
   int i, p, t;

   i = I[j]; H[i] = d;
   while (i > 1) {
      p = i / 2;
      if (H[p] < H[i]) break;
      t = H[p]; H[p] = H[i]; H[i] = t;
      t = V[p]; V[p] = V[i]; V[i] = t;
      I[V[i]] = i; I[V[p]] = p;
      i = p;
   }
}

void SSSP ( graph S, int n, int s, int t, int noshare )
{
   int N, src, tgt, i, j, d, nsteps, cost;
   int *D, *H, *V, *I, *prev;
   node *p;

   N = S.n; src = s*n+t; tgt = t*n+s;
   D = (int *)malloc(N * sizeof(int));
   H = (int *)malloc(N * sizeof(int));
   V = (int *)malloc(N * sizeof(int));
   I = (int *)malloc(N * sizeof(int));
   prev = (int *)malloc(N * sizeof(int));
   H[0] = 0;
   for (i=j=0; i<N; ++i) {
      prev[i] = src;
      if (i == src) {
         D[i] = 0;
         I[i] = UNDEFINED;
      } else if ((noshare) && (i / n == i % n)) {
         D[i] = INFINITY;
         I[i] = UNDEFINED;
      } else {
         D[i] = INFINITY;
         ++j; ++(H[0]);
         H[j] = INFINITY;
         V[j] = i;
         I[i] = j;
      }
   }
   p = S.adjlist[src];
   while (p) {
      i = p -> nbr;
      p = p -> next;
      if ((noshare) && (i / n == i % n)) continue;
      j = I[i]; D[i] = H[j] = S.vwt[src];
   }
   makeheap(H,V,I);

   while (H[0] > 0) {
      i = V[1];
      if (i == tgt) break;
      delmin(H,V,I);
      p = S.adjlist[i];
      while (p) {
         j = p -> nbr;
         if (I[j] != UNDEFINED) {
            d = D[i] + S.vwt[i];
            if (d < H[I[j]]) {
               D[j] = d;
               reducedist(H,V,j,d,I);
               prev[j] = i;
            }
         }
         p = p -> next;
      }
   }

   if ((H[0] == 0) || (D[tgt]==INFINITY)) {
      printf("    The puzzle is not solvable\n");
   } else {
      printf("    Steps:"); nsteps = cost = 0;
      showsoln(S,n,s*n+t,t*n+s,prev,&nsteps,&cost); printf("\n");
      printf("    Number of steps = %d\n", nsteps);
      printf("    Total effort    = %d\n", cost);
   }

   free(H); free(V); free(I); free(prev);
}

int main ( int argc, char *argv[] )
{
   int n, s, t;
   graph G, GR, GS;

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%d", &n);
   printf("n = %d\n", n);
   G = geninput(n);
   printf("\n+++ Input graph\n"); prngraph(G);

   GR = genrgraph(G);
   printf("\n+++ Reachability graph\n"); prngraph(GR);

   GS = gensrgraph(GR);
   printf("\n+++ Simultaneous reachability graph\n"); prngraph(GS);

   getst(GS,n,&s,&t);
   printf("\ns = %d\nt = %d\n", s, t);

   printf("\n+++ Minimum number of steps\n");

   printf("--- Allowing robots to share a node\n");
   BFS(GS,n,s,t,0);

   printf("--- Disallowing robots to share a node\n");
   BFS(GS,n,s,t,1);

   printf("\n+++ Minimum total combined effort\n");
   printf("--- Allowing robots to share a node\n");
   SSSP(GS,n,s,t,0);

   printf("--- Disallowing robots to share a node\n");
   SSSP(GS,n,s,t,1);

   exit(0);
}