AOJ0244 Bicycle Diet

解法

---

H,D,C,Lを適当に数字に置き換えて一つにまとめてしまう。
あとは既に行ったケーキ屋さんの情報をbitで持たせて幅優先するだけ。
微妙にバグったけど察して修正した。
最初ケーキ屋さんの数が100に見えて怖かった。問題文はちゃんと読もう(戒め)

ソース

---

#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<cstdlib>
using namespace std;
#define fr first
#define sc second
#define INF ( 1 << 30 )
int m, n, k, d;
int min_cost[110][1 << 6];
vector< int > cal;
typedef pair < int , int > Pi;
typedef pair < int , Pi > Pii;
struct edge{
  int to, cost;
  edge(){}
  edge( int to, int cost): to(to), cost(cost){};
};
vector < edge > info[110];
int java(string& s){
  if(s[0] == 'H') return 0; //MyHome
  if(s[0] == 'D') return 1; //市役所
  if(s[0] == 'C') return atoi(s.substr(1).c_str()) + 1; //ケーキ屋さん
  if(s[0] == 'L') return atoi(s.substr(1).c_str()) + m + 1; //ランドマーク
}
int bfs(){
  int ret = INF;
  fill_n(*min_cost,110*(1<<6),INF);
  queue< Pii > que;
  que.push(Pii( 0, Pi( 0, (1<<m) - 1)));
  min_cost[0][(1<<m)-1] = true;
  while(!que.empty()){
    Pii p = que.front();
    que.pop();
    if(p.sc.fr == 1) ret = min( ret, p.fr);
    if(min_cost[p.sc.fr][p.sc.sc] < p.fr ) continue;
    for(int i = 0 ; i < info[p.sc.fr].size() ; i++ ){
      edge e = info[p.sc.fr][i];
      int cost = p.fr + e.cost * k, bit = p.sc.sc;
      if( e.to >= 2 && e.to < 2 + m ){
        if((bit >> (e.to-2)) & 1){
          cost -= cal[e.to-2];
          bit &= ~(1 << (e.to-2));
        }else continue;
      }
      if( cost < min_cost[e.to][bit] ){
        que.push(Pii( cost,Pi( e.to, bit)));
        min_cost[e.to][bit] = cost;
      }
    }
  }
  return ret;
}
int main(){
  while(cin >> m >> n >> k >> d , m){
    cal.resize(m);
    for(int i = 0 ; i < m ; i++ ){
      cin >> cal[i];
    }
    for(int i = 0 ; i < d ; i++ ){
      string s1, s2;
      int cost;
      cin >> s1 >> s2 >> cost;
      info[java(s1)].push_back(edge( java(s2), cost));
      info[java(s2)].push_back(edge( java(s1), cost));
    }
    cout << bfs() << endl;
    for(int i = 0 ; i < 110 ; i++ ) info[i].clear();
  }
}