AOJ : 1311 - Test Case Tweaking

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1311
有向グラフが与えられます。
ノード１からノードＮまで、コストＣ以下で到達するためには、最小でいくつのエッジのコストを書きかえればいいでしょうか。
エッジのコストは、最小で０まで変更することができます。

アルゴリズム

エッジのコストはいくらにでも変更することができるので、明らかに０に変更した方がいい。

次の状態を保持して、ダイクストラ法で解きましょう。

• 今いるノードの番号
• 今までコストを０にしたエッジの個数
• コスト

closedリストは、[100(ノード番号)][1000(0にしたエッジ数)]の大きさにしたいところですが、実は[100][100]で事足ります。
あるノードに行きつくのに、1000個もエッジのコストを0に必要はなく、最大でもノード数の個数分だけ、0にすればいいからです。

プログラム

typedef pair<int,int> P;

class State{
public:
  int id,del,cost; //ノード番号, 0にしたエッジの個数, コスト
  State(){}
  State(int _id,int _del,int _cost){
    id = _id;
    del = _del;
    cost = _cost;
  }

  bool operator<(const State &st)const{
    return cost > st.cost;
  }
};

int n,m,c;
vector<P> t[102];
bool closed[102][102];

int main(void){
  while(scanf("%d%d%d",&n,&m,&c),n||m||c){
    rep(i,n+1) t[i].clear();
    rep(i,m){
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      t[a].push_back(P(b,c));
    }

    priority_queue<State> open;
    open.push(State(1,0,0));
    memset(closed,0,sizeof(closed));

    int ans = INT_MAX;

    while(!open.empty()){
      State st = open.top(); open.pop();
      if(closed[st.id][st.del]) continue;
      closed[st.id][st.del] = true;

      if(st.id == n){
        ans = min(ans,st.del);
        continue;
      }

      rep(i,t[st.id].size()){
        P e = t[st.id][i];
        //エッジのコストを変更しない
        if(st.cost + e.second <= c && !closed[e.first][st.del]){
          open.push(State(e.first,st.del,st.cost+e.second));
        }
        //エッジのコストを0に変更する
        if(st.del+1 <= n && !closed[e.first][st.del+1]){
          open.push(State(e.first,st.del+1,st.cost));
        }
      }
    }

    printf("%d\n",ans);
  }
}