土下座しながら探索中

主に競技プログラミング

AOJ 1311 : Test Case Tweaking

問題リンク : Test Case Tweaking | Aizu Online Judge

問題概要:
N個のノードからなる重み付き有向グラフが与えられる
そのグラフのノード1からノードNにいくための最小コストをcにするため重みを変更しなくてはならないエッジの数の最小値を答えよ

使用した言語:C++

解法;
mincost[a][b] := ノード1からノードaにb回エッジを変更して到達した時の最小コスト という配列を用意してダイクストラ法で解いた
dequeには今いる場所、これまでにエッジの重みを変更した回数、これまでにかかったコスト、これまでに通ったエッジの重みをもったプライオリティーキューを要素としてもたせた
別のノードに移動した時に、もしそれまでにかかった値と新たな値でcを越えてしまった場合にはプライオリティーキューのトップにある値を引いて値をc以下にする
というのもエッジの値を変更するのであればそれまでに通ったなかで一番重いエッジを0にしたほうが良いから
上記の操作を行うことでノードNに到達した地点でコストはc以下であることは保証される


コード:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cassert>
#include<deque>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef vector<P> VP;
typedef vector<VP> VVP;
 
int n,m,c;
int mincost[100][1000];//mincost[a][b] := aにb回チェンジしてきたときの最小値
struct Pox
{
  int p;
  int pop_cost;
  int cost;
  priority_queue<int> Q;
  Pox(int p=-1,int cost =-1,int pop_cost=-1,priority_queue<int> Q=priority_queue<int>()):p(p),cost(cost),pop_cost(pop_cost),Q(Q){}
};
 
void Input(VVP& G)
{
  for(int i=0;i<m;i++)
    {
      int f,t,c;
      cin >> f >> t >> c;
      f--,t--;
      G[f].push_back(P(t,c));
    }
}
 
 
 
int main()
{
 
  while(cin >> n >> m >> c,n|m|c)
    {
      VVP G(n);
 
      Input(G);
      rep(i,n)rep(k,m)mincost[i][k] = (1<<29);
      rep(i,m)mincost[0][i] = 0;
      deque<Pox> deq;
      deq.push_back(Pox(0,0,0,priority_queue<int>() ));
      int ans = (1<<29);
 
      while(!deq.empty())
    {
      Pox pox = deq.front(); deq.pop_front();
      if(pox.pop_cost >= ans)
        continue;
      if(pox.p == n-1)
        {
          assert(pox.cost <= c);
          ans = min(ans,pox.pop_cost);
          continue;
        }
 
      rep(i,G[pox.p].size())
        {
          int next = G[pox.p][i].first;
          int ncost = G[pox.p][i].second+pox.cost;
          int pcost = pox.pop_cost;
          priority_queue<int> q = pox.Q;
          q.push(G[pox.p][i].second);
          if(ncost > c)
        {
          while(ncost > c)
            {//1回しか行われない
              assert(!q.empty());
              ncost -= q.top();
              q.pop();
              pcost++;
            }
        }
          if(mincost[next][pcost] > ncost)
        {
          mincost[next][pcost] = ncost;       
          deq.push_back(Pox(next,ncost,pcost,q));
        }
        }
    }
      cout << ans << endl;
    }
  return 0;
}