AOJ : 1048 - Provident Housewife

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1048&lang=jp
日本語の問題文なので説明は省略

アルゴリズム

次の状態で遷移させて, ダイクストラ法で解きました.

• 今いるスーパーの番号
• すでに購入した商品 (ビット管理)
• 購入金額合計 (比較優先１)
• 歩いた距離 (比較優先２)

ちなみにJavaで解くと, 2秒かかってTLEだったので, いちいちC++で書き直して, 無理やり通しましたｗ
他の人は, ダイクストラではない方法で解いてるみたいです.
みなさん, 僕よりかなり実行速度が速いので, 他の人の解法も検索してみるといいと思います.

プログラム

class P{
public:
  int id,bought,price,walk;

  P(int _id,int _bought,int _price,int _walk){代入処理省略}
  bool operator<(const P &p)const{
    if(price == p.price) return walk > p.walk;
    return price > p.price;
  }
};

int t[12][12],market[12][16];
bool closed[12][33000];
vector<string> name[12];
vector<int> price[12];

int main(void){
  int n;

  while(cin>>n,n){
    rep(i,n){
      int k; cin>>k;
      name[i] = vector<string>(k);
      price[i] = vector<int>(k);
      rep(j,k) cin>>name[i][j]>>price[i][j];
    }

    int q; cin>>q;
    string list[q];
    rep(i,q) cin>>list[i];

    memset(t,0,sizeof(t));
    int m;
    cin>>m;
    rep(i,m){
      int a,b,cost;
      cin>>a>>b>>cost;
      t[a][b] = t[b][a] = cost;
    }

    memset(market,-1,sizeof(market));
    rep(i,n){
      rep(j,name[i].size()){
        rep(k,q){
          if(list[k] == name[i][j]){
            market[i][k] = price[i][j];
          }
        }
      }
    }

    priority_queue<P> open;
    memset(closed,0,sizeof(closed));
    open.push(P(0,0,0,0));
    P ans(0,0,0,0);

    while(!open.empty()){
      P p = open.top(); open.pop();
      if(closed[p.id][p.bought]) continue;
      closed[p.id][p.bought] = true;

      if(p.id == 0 && p.bought == (1<<q)-1){
        ans = p;
        break;
      }

      for(int i=0;i<=n;i++){
        if(t[p.id][i] > 0){
          open.push(P(i,p.bought,p.price,p.walk+t[p.id][i]));
        }
      }

      if(p.id > 0){
        int idx = p.id - 1;
        for(int i=0;i<q;i++){
          if(market[idx][i] > 0){
            open.push(P(p.id,p.bought|(1<<i),p.price+market[idx][i],p.walk));
          }
        }
      }
    }

    if(ans.bought == 0)
      cout<<"impossible\n";
    else
      cout<<ans.price<<" "<<ans.walk<<endl;
  }

  return 0;
}