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"); }