PKU 3411 Paid Roads

http://poj.org/problem?id=3411
n個のノードとm個の有向辺がある。
それぞれの辺を渡るときには以下のようなルールでコストが決められる。
もし、その辺を渡る前にノードcを訪れていれば、コストpで、
そうでなければ、コストrが必要になる。
このときに、ノード1からノードnまで行くのに必要な最小のコストを求めるというような問題。

訪れた辺を状態として持ってダイクストラする。

vector<pair<PI,PI> > G[10];
bool vis[10][1<<10];

main(){
  int n,m;
  cin>>n>>m;
  rep(i,m){
    int a,b,c,p,r;
    cin>>a>>b>>c>>p>>r;
    G[a-1].pb(mp(mp(b-1,c-1),mp(p,r)));
  }

  priority_queue<pair<int,PI> >q;
  q.push(mp(0,mp(0,0)));

  while(!q.empty()){
    int cc=-q.top().F,v=q.top().S.F,st=q.top().S.S;
    st|=1<<v;
    q.pop();
    if(vis[v][st])continue;
    vis[v][st]=true;
    if(v==n-1){
      cout<<cc<<endl;
      return 0;
    }
    rep(i,SZ(G[v])){
      int b=G[v][i].F.F,c=G[v][i].F.S,p=G[v][i].S.F,r=G[v][i].S.S;
      int nc=cc+(((st>>c)&1)?p:r);
      if(vis[b][st])continue;
      q.push(mp(-nc,mp(b,st)));
    }
  }
  puts("impossible");
}