1.cpp

#include <cassert>
#include <cstring>
#include <cstdio>

#include <string>
#include <vector>

#include <algorithm>
#include <iostream>

using namespace std;

#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define TRACE(x) cout << #x << " = " << (x) << endl

typedef long long llint;

const int MAXN = 330;
const int MAXD = 2020;

struct road {
  int next, len, marker, city, angle, ind, other;
};

bool bio[MAXN];
bool is_choice[MAXN];

bool ima[MAXN][MAXD];
int d[MAXN][MAXD];

vector<int> E[MAXN];
road r[MAXN];

int findNext(int i, int x) {
  int mindiff = 1000, who = -1;
  REP(j, (int)E[i].size()) 
    if (!bio[r[E[i][j]].ind]) {
      int y = E[i][j];
      int dl = (r[y].angle - (r[x].angle + 180) + 720)%360;
      int dr = 360-dl;
      if (dl <= dr) {
        if (dl <= mindiff) mindiff = dl, who = y;
      } else
        if (dr < mindiff) mindiff = dr, who = y;
    }

  return who;
}

int main(void)
{
  int ncp, nroads, ncm, confdist, start, end, startdir;
  int tp = 0;
  
  while (scanf("%d %d %d %d %d %d %d", &ncp, &nroads, &ncm, &confdist, &start, &end, &startdir) == 7) {
    if (!ncp && !nroads && !ncm && !confdist && !start && !end && !startdir) break;
    tp++;
    
    int n = 110; // intersections
    
    REP(i, n) {
      is_choice[i] = false;
      E[i].clear();
    }

    REP(i, ncp) {
      int x;
      scanf("%d", &x);
      is_choice[x] = true;
    }
    
    int m = 0; // road counter
    REP(i, nroads) {
      int a, b, dir_a, dir_b, len;
      scanf("%d %d %d %d %d", &a, &b, &dir_a, &dir_b, &len);
      m += 2;

      r[m-2] = (road){-1, len, 0, b, dir_a, i, m-1};
      r[m-1] = (road){-1, len, 0, a, dir_b, i, m-2};
      E[a].push_back(m-2);
      E[b].push_back(m-1);
    }

    REP(i, ncm) {
      int x, e, d;
      scanf("%d %d %d", &x, &e, &d); --e;
      REP(j, m)
        if (r[j].ind == e) {
          if (r[j].city != x) r[j].marker = d; else
            r[j].marker = r[j].len - d;
        }
    }

    REP(i, m) bio[i] = false;
    REP(i, n) REP(j, (int)E[i].size()) {
      bio[r[E[i][j]].ind] = true;      
      int next = findNext(r[E[i][j]].city, r[E[i][j]].other);
      r[E[i][j]].next = next;
      bio[r[E[i][j]].ind] = false;
    }

    REP(y, confdist+1) REP(x, m) {
      if (r[x].marker) {
        if (r[x].marker <= y) ima[x][y] = true, d[x][y] = r[x].marker; else
          ima[x][y] = false, d[x][y] = y;
      } else {
        if (r[x].len >= y || is_choice[r[x].city] || r[x].next == -1) ima[x][y] = false, d[x][y] = min(y, r[x].len); else
          ima[x][y] = ima[r[x].next][y - r[x].len], d[x][y] = d[r[x].next][y - r[x].len] + r[x].len;
      }
    }

    int x = -1;
    REP(j, (int)E[start].size())
      if (r[E[start][j]].angle == startdir) x = E[start][j];
    assert(x != -1);

    int lenHare = 0, lenHound = 0;
    static vector<int> ans;
    ans.clear();

    while (r[x].city != end) {
      int next = r[x].next;
      
      if (is_choice[r[x].city]) {
        int i = r[x].city;
        
        static vector<int> tmp; tmp.clear();

        bool found_marker = false;
        int curr = r[x].other;
        bio[r[curr].ind] = true;
        tmp.push_back(r[curr].ind);

        while (!found_marker) {
          curr = findNext(i, curr);
          bio[r[curr].ind] = true;
          tmp.push_back(r[curr].ind);

          if (ima[curr][confdist]) found_marker = true; else
            lenHound += 2*d[curr][confdist];
        }
        REP(j, (int)tmp.size()) bio[tmp[j]] = false;
        next = curr;
      }

      lenHare += r[x].len, lenHound += r[x].len;
      ans.push_back(x);
      x = next;
    }

    lenHare += r[x].len, lenHound += r[x].len;
    ans.push_back(x);

    printf("Case %d:\n", tp);
    printf("   Length of hare's route is %d\n", lenHare);
    printf("   Length of hound's search is %d\n", lenHound);
    printf("   Route:");
    REP(i, (int)ans.size())
      printf(" %d", r[ans[i]].ind+1);
    printf("\n\n");
    
  }
  return 0;
}