travel.c

#include <stdio.h>
#include <string.h>

int main()
{
  int n, roads, min, i, j, k, l, u, v;
  while (scanf("%d %d %d", &n, &roads, &min) == 3 && n != 0)
  {
    char A[n][n], P[n][n], tmp[n][n];
    int n2 = n * n;
    memset(A, 0, n2);

    // get input
    for (i = 0; i < roads; i++) {
      scanf("%d %d", &u, &v);
      A[u][v] = 1;
    }

    // P <-- A
    memcpy(P, A, n2);
    int best = -1;
    // for increasing path length l
    for (l = 2; l <= 22; l++) {
      // path found with len that exceeds minimum?
      if (P[0][n - 1] > 0 && l >= min) {
        best = l;
        break;
      }
      // tmp <-- P * A
      for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
          tmp[i][j] = 0;
          for (k = 0; k < n; k++)
            tmp[i][j] |= P[i][k] & A[k][j];
        }
      }
      // P <-- tmp
      memcpy(P, tmp, n2);
    }

    // output
    if (best == -1)
      puts("LOSER");
    else printf("%d\n", best);
  }
  return 0;
}