AOJ 2021 Princess in Danger
i番目の町にいて残り時間がjである状態を(i,j)としてこれらの状態間を移動にかかる時間ないしは経過時間をコストとする辺でつなぎ、グラフを作る。あとはDijkstra
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define INF 1000000 struct edge{int to,cost;}; typedef vector<edge> edges; typedef pair<int,int> P; void dijkstra(vector<edges> &g,vector<int> &dist,int s){ int v=g.size(); dist.assign(v,INF);dist[s]=0; priority_queue<P, vector<P>,greater<P> > que; que.push(P(0,s)); while(!que.empty()){ P p=que.top();que.pop(); int vp=p.second; if(dist[vp]<p.first) continue; REP(i,g[vp].size()){ edge e=g[vp][i]; if(dist[e.to]>dist[vp]+e.cost){ dist[e.to]=dist[vp]+e.cost; que.push(P(dist[e.to],e.to)); } } } } int main(){ int N,M,L,K,A,H; while(cin >> N >> M >> L >> K >> A >> H && N){ vector<bool> fr(N,false); vector<edges> g(N*(M+1)); fr[A]=true; fr[H]=true; REP(i,L){ int tmp; cin >> tmp; fr[tmp]=true; } REP(i,K){ int X,Y,T; cin >> X >> Y >> T; for(int j=T;j<=M;j++){ int xk=X*(M+1)+j-T; int yk=Y*(M+1)+j-T; g[X*(M+1)+j].push_back((edge){yk,T}); g[Y*(M+1)+j].push_back((edge){xk,T}); } } REP(i,N)REP(j,M){ if(fr[i]) g[i*(M+1)+j].push_back((edge){i*(M+1)+j+1,1}); } vector<int> dist(N*(M+1)); dijkstra(g,dist,A*(M+1)+M); int res=INF; REP(i,M+1){ res=min(res,dist[H*(M+1)+i]); } if(res==INF) cout << "Help!" << endl; else cout << res << endl; } return 0; }