UVa 10801 - Lift Hopping

#include <stdio.h>

int main() {
  int n, i, j, k, E;
  while (scanf("%d %d", &n, &E) == 2) {
    getchar();
    int t[100];
    for (i = 0; i < n; i++) {
      scanf("%d", &t[i]);
      getchar();
    }
    int max[5] = {}, d[5][100], visit[5][100] = {}, ok[5][100] = {};
    for (i = 0; i < 5; i++)
      for (j = 0; j < 100; j++)
        d[i][j] = 1e9;
    for (i = 0; i < n; i++) {
      char temp[200];
      gets(temp);
      int sum = 0;
      for (j = 0; ; j++)
        if ('0' <= temp[j] && temp[j] <= '9') {
          sum = sum * 10 + temp[j] - '0';
        } else {
          ok[i][sum] = 1;
          max[i] = sum > max[i] ? sum : max[i];
          if (!sum) d[i][0] = 0;
          sum = 0;
          if (!temp[j]) break;
        }
    }
    int ans = -1;
    while (1) {
      int type = -1, h, min = 1e9;
      for (i = 0; i < n; i++)
        for (j = 0; j <= max[i]; j++)
        if (ok[i][j] && !visit[i][j] && d[i][j] < min) {
          min = d[i][j];
          type = i;
          h = j;
        }
        if (type == -1) break;
        if (h == E) {
          ans = min;
          break;
        }
        visit[type][h] = 1;
        for (i = 0; i < n; i++)
          for (j = 0; j <= max[i]; j++)
            if (ok[i][j] && !visit[i][j]) {
              int w = d[type][h] + t[i] * ((j - h) < 0 ? (h - j) : (j - h));
              if (i == type) {
                if (w < d[i][j]) d[i][j] = w;
              } else if (j == h) {
                if (w + 60 < d[i][j]) d[i][j] = w + 60;
              }
            }
    }
    if (ans != -1) printf("%d\n", ans);
    else puts("IMPOSSIBLE");
  }
  return 0;
}