graveyard.cc

#include <cstdio>
#include <cstring>
#include <vector>
#include <limits>

#define GRAVE 2
#define HOLE 1
#define START 3
#define END 4
#define NONE 0
#define x first
#define y second
#define mp make_pair

using namespace std;
typedef pair<int, int> Point;

const int INF = 1e9;
const int N = 1000;
int n, W, H, G, E;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int d[N], board[40][40];

int encode(Point p) {
  return (p.x * H + p.y);
}

int m, last[N], to[4*N], next[4*N], weight[4*N], from[4*N];
void add_edge(Point p1, Point p2, int w) {
  int u = encode(p1);
  int v = encode(p2);
  from[m] = u;
  to[m] = v;
  weight[m] = w;
  next[m] = last[u];
  last[u] = m++;
}

bool validi(int i) {
  return (i >= 0 && i<W);
}
bool validj(int j) {
  return (j >= 0 && j<H);
}

bool relax() {
  bool relaxed = false;
  for (int e = 0; e<m; e++) {
    int u = from[e], v = to[e], w = weight[e];
    if (d[u]< d[v] - w) {
      relaxed = true;
      d[v] = d[u] + w;
    }
  }
  return relaxed;
}

bool bellman() {
  for (int i = 0; i<n; i++)
    d[i] = INF;
  d[0] = 0;
  for (int i=0; i<n; i++) {
    relax();
  }
  /*
  for (int e = 0; e<m; e++) {
    printf("(%d, %d)=%d\n", from[e], to[e], weight[e]);
  }
  for (int u =0; u<4; u++)
    printf("u=%d, d[u]=%d\n", u, d[u]);
    */
  bool hasCycle = relax();
  return hasCycle;
}

void init() {
  for (int i=0; i<W; i++)
    for (int j=0; j<H; j++)
      board[i][j] = NONE;
  board[0][0] = START;
  board[W-1][H-1] = END;
  m = 0;
  memset(last, -1, sizeof last);
}

int main() {
  while (scanf("%d %d", &W, &H)) {
    if (W == 0 && H == 0) break;
    init();
    n = W*H;
    scanf("%d", &G);
    for (int i=0; i<G; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      board[x][y] = GRAVE;
    }
    scanf("%d", &E);
    for (int i=0; i<E; i++) {
      int x1, y1, x2, y2, t;
      scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &t);
      board[x1][y1] = HOLE;
      add_edge(mp(x1, y1), mp(x2, y2), t);
    }
    /*
    for (int i=0; i<W; i++){
      for (int j=0; j<H; j++)
        printf("%d ", board[i][j]);
      printf("\n");
    }
    */
    for (int i=0; i<W; i++) {
      for (int j=0; j<H; j++) {
        if (board[i][j] == GRAVE) continue;
        if (board[i][j] == HOLE) continue;
        if (board[i][j] == END) continue;
        for (int k=0; k<4; k++) {
          if (validi(i+dx[k]) && validj(j+dy[k]))
            if (board[i+dx[k]][j+dy[k]] != GRAVE) 
              add_edge(mp(i, j), mp(i+dx[k], j+dy[k]), 1);
        }
      }
    }
    //printf("there are %d edges\n", m);
    bool hasCycle = bellman();
    if (hasCycle) {
      printf("Never\n");
    } else {
      int u = encode(mp(W-1, H-1));
      if (d[u] == INF) printf("Impossible\n");
      else printf("%d\n", d[u]);
    }
  }
  return 0;
}