#include<bits/stdc++.h>
using namespace std;
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をしてあげるべきである。