Problem 2021 : Princess in Danger

Princess in Danger

お姫様の危機
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2021

• 問題概要

たくさんの街と道とその距離が与えられる。
お姫様が怪我したので首都から血を送らないといけない。
しかし、血は一定時間で溶けてつかえなくなるので、途中で冷凍しないといけない。
冷凍できる街の番号と血が最大冷凍できる時間があたえられる。
最短で血をとどけろ、届けられないならhelp!!

• 解法

場所と血の残り時間を次元にした拡張ダイクストラ。
priority_queueを使わないと間に合わない。

• ソース

#include<iostream>
#include<algorithm>
#include<queue>

#define INF 1<<19

using namespace std;

class State{
public:
  int cost, blood, pos;
  bool operator < (const State s)const{
    if(cost != s.cost){
      return cost > s.cost;
    }
    return false;
  }
};

main(){
  
  int node, limit, freeze, road, start, goal;

  while( cin >> node >> limit >> freeze >> road >> start >> goal){
    if(node + limit  == 0)break;
    
    bool f[node];
    fill(f, f+node, false);
    for(int i=0; i<freeze; i++){
      int tmp;
      cin >> tmp;
      f[tmp] = true;
    }

    limit++;
    int edge[node][node];
    fill(&edge[0][0], &edge[node-1][node], INF);
    int cost[node][limit];
    fill(&cost[0][0], &cost[node-1][limit], INF);
    bool visited[node][limit];
    fill(&visited[0][0], &visited[node-1][limit], false);

    for(int i=0; i<road; i++){
      int f, to, c;
      cin >> f >> to >> c;
      edge[f][to] = edge[to][f] = c;
    }
    
    priority_queue<State> Q;
    State s;
    s.cost = 0;
    s.blood = limit-1;
    s.pos = start;
    cost[start][limit-1] = 0;
    
    Q.push(s);
    bool flag = false;
    int ans=0;
    while(!Q.empty()){
      State now = Q.top();
      Q.pop();

      int npos = now.pos;
      if(npos == goal){
	flag = true;
	ans = now.cost;
	break;
      }
      if(visited[npos][now.blood])continue;
      visited[npos][now.blood] = true;
      
      int nc = now.cost;
      int nb = now.blood;
      for(int i=0; i<node; i++){ 
	if(edge[npos][i] == INF)continue;
	for(int j=0; j+nb<limit; j++){
	  if(!f[npos] && j != 0)break;
	  int pc = nc + j + edge[npos][i];
	  int pb = nb + j - edge[npos][i];
	  if(pb < 0)continue;	  
	  if(visited[i][pb])continue;
	  if(cost[i][pb] > pc){
	    cost[i][pb] = pc;
	    s.pos = i;
	    s.blood = pb;
	    s.cost = pc;
	    Q.push(s);
	  }
	}
      }
    }

    if(flag)cout << ans << endl;
    else cout << "Help!" << endl;
  }
}

リベンジが果たせた。