PKU : 3411 - Paid Roads

問題概要

http://poj.org/problem?id=3411

片方向グラフが与えられます.
あるエッジ i を通るときのコストは, ciをすでに訪れたことがある場合 Piかかり, 訪れたことがない場合 Ri かかります.
このとき, ノード１からNまでの最短コストを求めてください.

アルゴリズム

Nが10以下なので, ビットで訪れたことのあるノードを管理し, ダイクストラしました.

反省

• "two ways"というのを見て, 双方向だと勘違いした

プログラム

class Edge{
public:
  int a,b,c,p1,p2;
  Edge(){}
  Edge(int _a,int _b,int _c,int _p1,int _p2){
    a = _a;
    b = _b;
    c = _c;
    p1 = _p1;
    p2 = _p2;
  }
};

class State{
public:
  int id,cost,bit;
  State(){}
  State(int _id,int _cost,int _bit){
    id = _id;
    cost = _cost;
    bit = _bit;
  }

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

int n,m;
vector<Edge> t[11];

int main(void){
  cin>>n>>m;

  rep(i,m){
    int a,b,c,p1,p2;
    cin>>a>>b>>c>>p1>>p2;
    t[a].push_back(Edge(a,b,c,p1,p2));
  }

  priority_queue<State> open;
  bool closed[n+1][1<<(n+1)];
  open.push(State(1,0,2));
  memset(closed,0,sizeof(closed));

  State ans(-1,-1,-1);

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

    if(st.id == n){
      ans = st;
      break;
    }

    rep(i,t[st.id].size()){
      Edge e = t[st.id][i];
      int ncost = st.cost;
      if(st.bit & (1<<e.c)){
        ncost += e.p1;
      }
      else{
        ncost += e.p2;
      }
      open.push(State(e.b,ncost,st.bit|(1<<e.b)));
    }
  }

  if(ans.id == -1){
    cout<<"impossible\n";
  }
  else{
    cout<<ans.cost<<endl;
  }
}