Problem 0224 : Bicycle Diet
問題概要
日本語なので本文参照(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0224&lang=jp)
自宅から、ケーキ屋とランドマークからなるノードを通り役所まで行く。
ケーキ屋の前を通るときにはそのケーキ屋のケーキを食べ、カロリーを摂取する。
ケーキ屋の前は一度しか通ることができない。他のノードは何度でも通ることができる。
解法
ケーキ屋を通ったかどうかでノードを多重化してDijkstra.
ただし、グラフに負辺があるため訪問ノードをboolで管理する方法だとWAとなる。
各ノードまでの最短距離をテーブルで管理する必要がある。
ソースコード
int cake,land,calo,edge; int n,node; int gain[6],d[7000]; vector<vector<pi> > e; int id(char *s) { if(s[0]=='H')return n-2; if(s[0]=='D')return n-1; int num=atoi(s+1); if(s[0]=='C')return num-1; return num-1+cake; } int main() { while(scanf("%d%d%d%d",&cake,&land,&calo,&edge),calo) { n=cake+land+2; node=n*(1<<cake); e.clear(); e.resize(node); rep(i,cake)scanf("%d",gain+i); rep(i,edge) { char s1[9],s2[9]; int t; scanf("%s%s%d",s1,s2,&t); int t1=id(s1),t2=id(s2); t*=calo; e[t1].pb(mp(t2,t)); e[t2].pb(mp(t1,t)); } rep(i,node)d[i]=inf; d[(n-2)*(1<<cake)]=0; priority_queue<pi> Q; Q.push(mp(0,(n-2)*(1<<cake))); int ans=inf; while(!Q.empty()) { int cc=-Q.top().first,cnode=Q.top().second; Q.pop(); int bit=cnode%(1<<cake),cur=cnode/(1<<cake); if(cur==n-1)ans=min(ans,cc); if(d[cnode]>cc)continue; fr(i,e[cur]) { int nc=cc+i->second,nxt=i->first,nbit=bit; if(0<=nxt&&nxt<cake) { if(1<<nxt&bit)continue; nc-=gain[nxt]; nbit^=1<<nxt; } nxt=nxt*(1<<cake)+nbit; if(d[nxt]>nc)Q.push(mp(-nc,nxt)),d[nxt]=nc; } } printf("%d\n",ans); } return 0; }
誤答例
int cake,land,calo,edge,gain[6]; int n,node; bool v[7000]; vector<vector<pi> > e; int id(char *s) { if(s[0]=='H')return n-2; if(s[0]=='D')return n-1; int num=atoi(s+1); if(s[0]=='C')return num-1; return num-1+cake; } int main() { while(scanf("%d%d%d%d",&cake,&land,&calo,&edge),calo) { n=cake+land+2; node=n*(1<<cake); e.clear(); e.resize(node); rep(i,cake)scanf("%d",gain+i); rep(i,edge) { char s1[9],s2[9]; int t; scanf("%s%s%d",s1,s2,&t); int t1=id(s1),t2=id(s2); t*=calo; e[t1].pb(mp(t2,t)); e[t2].pb(mp(t1,t)); } rep(i,node)v[i]=0; priority_queue<pi> Q; Q.push(mp(0,(n-2)*(1<<cake))); int ans=inf; while(!Q.empty()) { int cc=-Q.top().first,cnode=Q.top().second; Q.pop(); int bit=cnode%(1<<cake),cur=cnode/(1<<cake); if(cur==n-1)ans=min(ans,cc); if(v[cnode])continue; v[cnode]=1; fr(i,e[cur]) { int nc=cc+i->second,nxt=i->first,nbit=bit; if(0<=nxt&&nxt<cake) { if(1<<nxt&bit)continue; nc-=gain[nxt]; nbit^=1<<nxt; } nxt=nxt*(1<<cake)+nbit; if(!v[nxt])Q.push(mp(-nc,nxt)); } } printf("%d\n",ans); } return 0; }