// meltyblood.cc by Yu Sugawara #include #include #include #include #include #include #include #include #include using namespace std; typedef int Point; typedef int Weight; struct Edge { Point destination; Weight w; Edge(){} Edge(Point p, Weight w): destination(p), w(w) {} }; typedef vector Edges; typedef map Graph; typedef map Potential; void makeEdges(Point p, Point q, Weight w, Graph& g) { g[p].push_back(Edge(q, w)); g[q].push_back(Edge(p, w)); } Potential dijkstra(Graph& g, Point start) { Potential pot; typedef pair Element; typedef priority_queue, greater > PQ; PQ todo; todo.push(Element(0, start)); while(!todo.empty()) { Weight current_length = todo.top().first; Point cur = todo.top().second; todo.pop(); if (pot.count(cur)) continue; pot[cur] = current_length; const Edges& es = g[cur]; for (Edges::const_iterator it = es.begin(); it != es.end(); ++it) { Point next = it->destination; if (pot.count(next)) continue; Weight next_length = current_length + it->w; todo.push(Element(next_length, next)); } } return pot; } struct EdgeInput { int from, to, weight; template void input(IN& in) { in >> from >> to >> weight; } template void output(OUT& out) const { out << from << " " << to << " " << weight << endl; } }; struct Problem { Problem(){} template bool input(IN& in) { refrigerator_.clear(); edges_.clear(); int nedges, nfridge; in >> nvertices_ >> ttmelt_ >> nfridge >> nedges >> start_ >> goal_; if (nvertices_ == 0 && ttmelt_ == 0 && nfridge == 0 && nedges == 0 && start_ == 0 && goal_ == 0) { return false; } assert(nvertices_ > 0); for (int i = 0; i < nfridge; ++i) { int f; in >> f; refrigerator_.push_back(f); } for (int i = 0; i < nedges; ++i) { EdgeInput e; e.input(in); edges_.push_back(e); } return true; } template void output(OUT& out) const { out << nvertices_ << " " << ttmelt_ << " " << refrigerator_.size() << " " << edges_.size() << " " << start_ << " " << goal_ << endl; if (refrigerator_.empty()) { out << endl; } else { out << refrigerator_[0]; for (size_t i = 1; i < refrigerator_.size(); ++i) out << " " << refrigerator_[i]; out << endl; } for (size_t i = 0; i < edges_.size(); ++i) { edges_[i].output(out); } return; } int nvertices_; vector refrigerator_; int ttmelt_; vector edges_; int start_, goal_; }; class Solution { public: Solution() {}; virtual ~Solution(){}; virtual int solve(const Problem& problem) = 0; }; class DualDijkstra : public Solution { public: virtual int solve(const Problem& problem); }; Graph graphFromProblem(const Problem& p) { Graph g; for (size_t i = 0; i < p.edges_.size(); ++i) { EdgeInput e = p.edges_[i]; // if (e.weight > p.ttmelt_) // continue; makeEdges(e.from, e.to, e.weight, g); } return g; } int DualDijkstra::solve(const Problem& problem) { Graph g(graphFromProblem(problem)); Graph nextg; vector refrigerator; refrigerator.push_back(problem.start_); refrigerator.push_back(problem.goal_); copy(problem.refrigerator_.begin(), problem.refrigerator_.end(), back_inserter(refrigerator)); for (size_t i = 0; i < refrigerator.size(); ++i) { Potential pot = dijkstra(g, refrigerator[i]); for (size_t j = i + 1; j < refrigerator.size(); ++j) { int target = refrigerator[j]; if (!pot.count(target)) continue; Weight w = pot[target]; if (w <= problem.ttmelt_) makeEdges(i, j, w * 2, nextg); } } Potential pot = dijkstra(nextg, 0); if (!pot.count(1)) return -1; int non_freeze_time = min(pot[1] / 2, problem.ttmelt_); return pot[1] - non_freeze_time; } int main(int argc, char** argv) { Problem p; while(p.input(cin)) { DualDijkstra dd; int answer = dd.solve(p); if (answer < 0) cout << "Help!" << endl; else cout << answer << endl; } return 0; }