AOJ 2021 - Princess in Danger

問題概要

最初ライフポイントがMであり、これは道を歩くことで単位時間あたりに1減少する。L個の町にはライフポイントの回復地点があり、ここでは単位時間あたりに1のライフポイントを回復でき最大Mまで回復することができる。K本の道があり、そこには時間が設けられている。このときライフポイントが0未満にならないようにスタート地点Aからゴール地点Hへの最短時間を求めよ。もし不可能な場合は"Help!"を出力せよ。

制約

• 2 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• 0 ≤ L ≤ N - 2
• 0 ≤ A < N
• 0 ≤ H < N

解法

dijkstra。
Time[どの町][残りのライフポイント] := 最短時間。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 110
#define INF 1e9
#define F first
#define S second
typedef pair<int,int> pii;
typedef pair<pii,int> State;
 
struct Edge{
  int to,cost;
  Edge(){}
  Edge(int to,int cost) : to(to),cost(cost) {}
};
 
int N,M,L,K,A,H;
bool l[MAX];
vector<Edge> G[MAX];
 
void init(){
  for(int i = 0 ; i < MAX ; i++){
    l[i] = false;
    G[i].clear();
  }
}
 
int dijkstra(){
  priority_queue<State,vector<State>,greater<State> > Q;
  Q.push(State(pii(0,A),M));
  
  int Time[MAX][MAX];
  fill(Time[0],Time[0]+MAX*MAX,INF);
  Time[A][M] = 0;
 
  while(!Q.empty()){
    State s = Q.top(); Q.pop();
    int v = s.F.S, m = s.S;
    if(Time[v][m] < s.F.F) continue;
 
    if(l[v]){
      for(int i = 1 ; i <= M-m ; i++){
        if(Time[v][m] + i < Time[v][m+i]){
          Time[v][m+i] = Time[v][m] + i;
          Q.push(State(pii(Time[v][m+i],v),m+i));
        }
      }
    }
 
    for(int i = 0 ; i < (int)G[v].size() ; i++){
      Edge e = G[v][i];
      if(m - e.cost >= 0){
        if(Time[v][m] + e.cost < Time[e.to][m-e.cost]){
          Time[e.to][m-e.cost] = Time[v][m] + e.cost;
          Q.push(State(pii(Time[e.to][m-e.cost],e.to),m-e.cost));
        }
      }
    }
  }
  return *min_element(Time[H],Time[H]+M);
}
 
int main(){
  int a,b,c;
  while(cin >> N >> M >> L >> K >> A >> H, N){
    init();
    for(int i = 0 ; i < L ; i++){
      cin >> a;
      l[a] = true;
    }
    for(int i = 0 ; i < K ; i++){
      cin >> a >> b >> c;
      G[a].push_back(Edge(b,c));
      G[b].push_back(Edge(a,c));
    }
    int res = dijkstra();
    if(res == INF){
      cout << "Help!" << endl;
    }else{
      cout << res << endl;
    }
  }
  return 0;
}