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