SRM 340 Div1 Medium CsCourses

問題

CSの授業がいくつか用意されており、i番目の授業にはtheoreticalValue[i]とpracticalValue[i]とexpire[i]という3つの数値が与えられている。各授業の履修期間は一ヶ月で、あなたはひと月に授業を一つだけ取ることができる。そしてあなたは理論スキルと実践スキルという2つのスキルがあり、thepreticalValue[i] <= 理論スキル + 1 かつ practicalValue[i] <= 実践スキル + 1 であるときのみ授業iを受けることができる（もちろん自分のスキルより低いレベルの授業も受けられる）。受講後にはあなたの理論スキルと実践スキルはtheoreticalValue[i]とpracticalValue[i]まで上昇する。ただし、低いレベルの授業を受けてもスキルが下降することはない。
また各授業には開講期間が設けられ、expire[i]ヶ月の後には授業iは受講できなくなる。

理論、実践の両スキルが共にskillBound以上になるために必要な、最短の受講パターンを求め、その順番を返せ。複数あるときは辞書式最小のものを返せ。

やりかた

理論、実践スキルがともに0の状態から幅優先探索でどちらともskillBound以上になるまで探索する。探索過程で、ある授業を選択するまでに要する期間が、その授業の終了時期よりあとになるようなら、その授業は選択しないようにする。あと、スキルが下降しないことに注意する。

struct skill{
  int idx, tvi, pvi;
  vector<int> path;
};
int d[60][60];

class CsCourses {
public:
  vector <int> getOrder(vector <int> theoreticalValue, vector <int> practicalValue, vector <int> expire, int skillBound){
    if(skillBound == 0) return vector<int>();
    int N = theoreticalValue.size();
    memset(d, -1, sizeof(d));
    
    d[0][0] = 0;
    queue<skill> Q;
    skill init;
    init.idx = -1, init.tvi = 0, init.pvi = 0;
    Q.push(init);

    while(!Q.empty()){
      skill s = Q.front(); Q.pop();
      //スキルがskillBound以上になったら終了
      if(s.idx != -1 && 
	 s.tvi >= skillBound && s.pvi >= skillBound) return s.path;
      
      for(int i = 0; i < N; i++){
	if(i == s.idx) continue;
　　　　//授業iが選択できる時、スキルを更新して探索を続行
	if(theoreticalValue[i] - s.tvi <= 1 && 
	   practicalValue[i] - s.pvi <= 1 &&
	   d[s.tvi][s.pvi] + 1 <= expire[i]){
	  skill t = s;
	  t.idx = i;
	  t.tvi = max(t.tvi, theoreticalValue[i]);
	  t.pvi = max(t.pvi, practicalValue[i]);
	  t.path.push_back(i);
	  if(d[t.tvi][t.pvi] == -1){
	    d[t.tvi][t.pvi] = d[s.tvi][s.pvi] + 1;
	    Q.push(t);
	  }
	}
      }
    }
    return vector<int>();
  }
};