POJ 3411 Paid Roads
問題
n個の都市がある。
1番の都市からn番の都市へ行きたい。
道路がm本あり、それぞれの道路は都市a[i]とb[i]を結んでいる。
道路を通るには交通料がかかり、
都市c[i]を事前に訪れている場合P[i]、そうでない場合R[i]のコストがかかる。
n番の都市へ行くのにかかるコストの最小値を求めよ。
n番の都市へ行くことが出来ない場合impossibleを出力せよ。
制約条件
n≦100
1≦a[i],b[i],c[i]≦n
P[i],R[i]≦100
方針
ビットDP.
すなわち、dp[i][j]を今都市iに、集合jの都市を事前に訪れているときの最小コストとする。
この表を更新するDPによりゴールへの最短コスト求まる。
グラフはサイクルを含む場合があるので、ベルマンフォードで更新した。
ソースコード
struct edge{ int a,b,c,p,r; }; int n,m; vector<vector<edge> > g; int dp[10][1<<10]; int main(){ scanf("%d%d",&n,&m); g.resize(n); rep(i,m){ edge e; scanf("%d%d%d%d%d",&e.a,&e.b,&e.c,&e.p,&e.r); e.a--; e.b--; e.c--; g[e.a].pb(e); } rep(i,n)rep(j,1<<n)dp[i][j]=(int)1e9; dp[0][1]=0; int ans=(int)1e9; rep(i,1<<n)rep(it,n)rep(j,n)rep(k,g[j].size()){ edge &e=g[j][k]; dp[e.b][i|1<<e.b]=min(dp[e.b][i|1<<e.b],dp[j][i]+(i&1<<e.c?e.p:e.r)); } rep(i,1<<n)ans=min(ans,dp[n-1][i]); if(ans==(int)1e9)puts("impossible"); else printf("%d\n",ans); return 0; }