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; }