1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| #include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P, int> PI;
typedef pair<P, P > PP;
struct edge {
int from,to;
int cost;
edge(int t,int c) : to(t),cost(c) {}
edge(int f,int t,int c) : from(f),to(t),cost(c) {}
bool operator<(const edge &e) const {
return cost < e.cost;
}
};
int n, m, l, k, a, h;
vector<edge> G[105];
int d[105][105];
bool L[105];
void dijkstra(int s) {
priority_queue<PI, vector<PI>, greater<PI> > que;
rep(i, 105) {
rep(j, 105) {
d[i][j] = INF;
}
}
d[s][m] = 0;
que.push(PI(P(0, m), s));
while(que.size()) {
PI p = que.top();
que.pop();
int cost = p.first.first;
int t = p.first.second;
int v = p.second;
if(d[v][t] < cost) continue;
if(L[v]) {
REP(i, t+1, m+1) {
if(d[v][i] > d[v][t] + (i - t)) {
d[v][i] = d[v][t] + (i - t);
que.push(PI(P(d[v][i], i), v) );
}
}
}
rep(i, G[v].size()) {
edge e = G[v][i];
int nt = t - e.cost;
if(nt >= 0 && d[e.to][nt] > d[v][t] + e.cost) {
d[e.to][nt] = d[v][t] + e.cost;
que.push(PI(P(d[e.to][nt], nt), e.to));
}
}
}
}
int main() {
while(cin >> n >> m >> l >> k >> a >> h) {
if(n == 0 && m == 0 && l == 0 && k == 0 && a == 0 && h == 0) break;
rep(i, 105) G[i].clear();
memset(L, 0, sizeof(L));
rep(i, l) {
int x;
cin >> x;
L[x] = true;
}
rep(i, k) {
int s, t, c;
cin >> s >> t >> c;
G[s].push_back(edge(t, c));
G[t].push_back(edge(s, c));
}
dijkstra(a);
int ans = INF;
rep(i, m + 1) {
ans = min(ans, d[h][i]);
}
if(ans == INF) cout << "Help!" << endl;
else cout << ans << endl;
}
return 0;
}
|