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