AOJ1318.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (X).begin(),(X).end()

using namespace std;

typedef int Weight;
const Weight INF = 1000000000;
struct Edge{
  int dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){dest, weight});
}

void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int v, n, m, cap, src, dest;
vector<int> c1, c2, d, s;

bool init() {
  cin >> n >> m >> cap;
  cap *= 10;
  if (n == 0) return false;
  string srcStr, destStr;
  cin >> srcStr >> destStr;
  vector<string> cc1(n), cc2(n), str(m);
  c1.assign(n, 0), c2.assign(n, 0), d.assign(n, 0); s.assign(m, 0);
  REP(i,n) cin >> cc1[i] >> cc2[i] >> d[i];
  REP(i,m) cin >> str[i];
  
  set<string> se;
  se.insert(srcStr); se.insert(destStr);
  REP(i,n) {
    se.insert(cc1[i]);
    se.insert(cc2[i]);
  }
  REP(i,m) se.insert(str[i]);
  map<string,int> hash;
  int cnt = 0;
  for (string c : se) hash[c] = cnt++;

  v = se.size();
  src = hash[srcStr]; dest = hash[destStr];
  REP(i,n) {
    c1[i] = hash[cc1[i]];
    c2[i] = hash[cc2[i]];
  }
  REP(i,m) s[i] = hash[str[i]];
  return true;
}

int main() {
  while (init()) {
    Graph g(v);
    Graph h(v);
    REP(i,n) {
      add_edge(g, c1[i], c2[i], d[i]);
      add_edge(g, c2[i], c1[i], d[i]);
    }
    s.push_back(src);
    REP(i,m+1) {
      Array d;
      dijkstra(g, d, s[i]);
      REP(j,v) if (d[j] <= cap) add_edge(h, s[i], j, d[j]);
    }
    Array d;
    dijkstra(h, d, src);
    int res = d[dest];
    cout << (res == INF ? -1 : res) << endl;
  }
  return 0;
}