読者です 読者をやめる 読者になる 読者になる

2011アジア地区予選福岡 D問題

WA・・・なんで・・・
→投げ直したら通った・・・謎現象。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <sstream>
#include <set>
#include <map>
#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> Q;

const int INF = 1000000000;

int n, m, l, vs;
bool fl[6005];
vector<int> to[6005], co[6005];
map<string,int> mp;
int d[6005][2005];
int e[6005];

int toi(string s){
    map<string,int>::iterator it = mp.find(s);
    if(it == mp.end()){
        mp.insert(make_pair(s,vs));
        return vs++;
    } else return (*it).se;
}

int main(){
	while (cin >> n >> m >> l, n) {
        l *= 10;
        mp.clear();
        vs = 0;
        string ss, ts, as, bs;
        cin >> ss >> ts;
        int a, b, c, s, t;
        rep(i,n){
            cin >> as >> bs >> c;
            a = toi(as);
            b = toi(bs);
            to[a].pb(b); co[a].pb(c);
            to[b].pb(a); co[b].pb(c);
            //printf("%d %d\n",a,b);
        }
        
        s = toi(ss);
        t = toi(ts);
        
        rep(i,vs) fl[i] = false;
        rep(i,m){
            cin >> as;
            a = toi(as);
            //printf("%d full\n",a);
            fl[a] = true;
        }
        rep(i,vs) e[i] = -1;
        
        priority_queue<Q,vector<Q>,greater<Q> > q;
        rep(i,vs)rep(j,l+1) d[i][j] = INF;
        q.push(Q(0,P(s,l)));
        d[s][l] = 0;
        while(q.size()){
            Q r = q.top(); q.pop();
            c = r.fi; a = r.se.fi; b = r.se.se;
            //printf("%d %d %d\n",a,b,c);
            if(d[a][b] != c) continue;
            if(fl[a]) b = l;
            e[a] = max(e[a],b);
            rep(i,to[a].size()){
                int v = to[a][i], x = co[a][i];
                if(b-x <= e[v] || d[v][b-x] <= c+x) continue;
                d[v][b-x] = c+x;
                q.push(Q(c+x,P(v,b-x)));
            }
        }
        
        int ans = INF;
        rep(i,l+1) ans = min(ans,d[t][i]);
        
        if(ans == INF) puts("-1");
        else printf("%d\n",ans);
        rep(i,vs){ to[i].clear(); co[i].clear();}
	}

	return 0;
}