はやし屋

競技プログラミングのメモ きたない

aoj 2021: Princess in Danger

やっとできた...
変なテンションで書いたわけわかんないコメントは無視

#include<iostream>
#include<vector>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

int n , m, l , k , a ,h;
// to cost 
struct edge{
  int t , c;
  edge(int t , int c):t(t),c(c) {};
};
// いまいる ぶじ こすと
struct P{
  int n , m , c;
  P(int n , int m , int c):n(n),m(m),c(c) {};
};

bool operator>(const P& l,const P& r){
  return l.c > r.c;
}

int hp[111];
vector < edge > edges[111];
int cost[111][111];

int dij(){
  priority_queue < P , vector < P > , greater < P > > que;
  que.push(P(a,m,0));
  cost[a][m] = 0;
  while(!que.empty()){
    //   cout << que.size() << endl;
    P p = que.top();que.pop();
    if(cost[p.n][p.m] < p.c)continue;
    if(p.n == h)return p.c;
    // hospital
    if(hp[p.n]){
      for(int i = p.m+1 ; i <= m ; ++i){
	// memo
	if(cost[p.n][i] > p.c+(i-p.m)){
	  cost[p.n][i] = p.c+(i-p.m);
	  que.push(P(p.n,i,p.c+(i-p.m)));
	}
      }
    }
    for(int i = 0 ; i < edges[p.n].size() ; ++i){
      edge t = edges[p.n][i];
      if(p.m < t.c)continue; // 間に合わない
      if(cost[t.t][p.m-t.c] > p.c+t.c){
	cost[t.t][p.m-t.c] = p.c+t.c;
	que.push(P(t.t,p.m-t.c,p.c+t.c));
      }
    }
  }
  return -1;
}

void init(){
  for(int i = 0 ; i < 111 ; ++i){
    edges[i].clear();
    for(int j = 0 ; j < 111 ; ++j){
      cost[i][j] = 1<<27;
    }
  }
  memset(hp,0,sizeof(hp));
}

int main(){

  while(cin >> n >> m >> l >> k >> a >> h &&
	(n|m|l|k|a|h)){
    init();
    for(int i = 0 ; i < l; ++i){
      int b ; cin >> b;
      hp[b]++;
    }
    for(int i = 0 ; i < k ; ++i){
      int q,w,c;cin >> q >> w >> c;
      edges[q].push_back(edge(w,c));
      edges[w].push_back(edge(q,c));
    }
    //    cout << "_OK_" << endl;
    int jud = dij();
    if(~jud)cout << jud << endl;
    else cout << "Help!" << endl;
  }
}

こういうのコンテスト中解けるようにしたいな