静かで孤独な日記

のんびりたまに

AOJ 2585 1 Day Passport

#include<bits/stdc++.h>
using namespace std;

/*
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2014/Practice/模擬国内予選/講評&openfile=D.pdf
*/

const int inf=1e9;

int main(){
  ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m,h,k;
	while(cin>>n>>m>>h>>k,n){
		vector<tuple<int,int,int,int> > v[101];
		for(int i=0;i<m;i++){
			int a,b,c,d,e;cin>>a>>b>>c>>d>>e;
			a--;b--;e--;
			v[a].push_back(make_tuple(b,c,d,e));
			v[b].push_back(make_tuple(a,c,d,e));
		}
		int s,t;cin>>s>>t;
		s--;t--;
		int p;cin>>p;
		int a[500],b[500];
		for(int i=0;i<p;i++){
			int l,d;cin>>l>>d;
			int now=0;
			for(int j=0;j<l;j++){
				int tmp;cin>>tmp;
				tmp--;
				now|=(1<<tmp);
			}
			a[i]=d;
			b[i]=now;
		}
		int dp[300][300];
		for(int i=0;i<300;i++)for(int j=0;j<300;j++)dp[i][j]=inf;
		dp[0][0]=0;
		for(int i=0;i<p;i++){
			for(int j=0;j<(1<<k);j++){
				dp[i+1][j|b[i]]=min(dp[i+1][j|b[i]],dp[i][j]+a[i]);
				dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
			}
		}
		int ans=inf;
		for(int i=0;i<(1<<k);i++){
			if(dp[p][i]==inf)continue;
			int d[101][25];
			for(int j=0;j<n;j++)for(int k=0;k<=h;k++)d[j][k]=inf;
			d[s][0]=0;
			priority_queue<tuple<int,int,int> > q;
			q.push(make_tuple(0,s,0));
			while(!q.empty()){
				int now=get<1>(q.top());
				int nowcost=-get<0>(q.top());
				int nowh=get<2>(q.top());
				q.pop();
				if(nowcost>d[now][nowh])continue;
				for(int j=0;j<(int)v[now].size();j++){
					int next=get<0>(v[now][j]);
					int next_h=get<2>(v[now][j]);
					int next_cost=get<1>(v[now][j]);
					int cop=get<3>(v[now][j]);
					if(i&(1<<cop))next_cost=0;
					if(nowh+next_h<=h && d[next][nowh+next_h]>d[now][nowh]+next_cost){
						d[next][nowh+next_h]=d[now][nowh]+next_cost;
						q.push(make_tuple(-d[next][nowh+next_h],next,nowh+next_h));
					}
				}
			}
			int res=inf;
			for(int j=0;j<=h;j++)res=min(res,d[t][j]);
			ans=min(res+dp[p][i],ans);
		}
		if(ans==inf)cout<<-1<<endl;
		else cout<<ans<<endl;
	}
}
  • これ、簡単だと思ってやったら1週間どハマりした(最悪)(でも良い経験になった)
  • どこでハマったかというと、dijkstraのところで、最初は各頂点への最短距離を持っておくd[N]を使って実装していて、提出してはWAをしていた。
  • これだと、時間と関係なくその頂点の最短距離を保存してしまうからダメ。
  • ダメな理由は、例えば1日がH時間だとして、ある頂点Vに行く行き方が「H-1時間でコスト100」と「H-3時間でコスト200」の2通りあったとする。そしてVから目的地Tまでは「2時間でコスト100」の一本だけがあったとしよう。
  • 前者の方法だとH-1時間でコスト100の内容しかd[V]に保存されず、これではTまで行くには最低H+1時間かかり答えは-1と出力されてしまう。
  • これは明らかに間違っていて、本来出力されるべき答えは300である。H-3時間でコスト200から2時間でTまで行き到着である。
  • このように、必ずしもコストが最小のものでゴールできるとは限らないのでd[頂点][かかった時間]としてdijkstraをしてあげるべきである。