はやし屋

競技プログラミングのメモ きたない

AOJ 2585: 1 Day Passport

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2585

ICPCに出ることになったので,久々に競プロしました.
dijkstraは忘れていなかったのでよかった.
問題が長かった.構造体の使い方忘れてた.
徹夜明けでもありバグがひどく出た.1月半後のICPCまでには極力減らしたい.


問題概要は省略.

bitdp + dijkstraで解きました.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
 
using namespace std;
 
typedef long long ll;    
typedef pair < int , int > Pi;    
typedef pair < int , Pi > Pii; 
   
#define INF (1 << 28)    
#define sz(z) (int)((z).size())
#define fr first    
#define sc second
#define reps(i,j,n) for(int i = j ; i < n ; ++i)    
#define rep(i, n) reps(i,0,n)    
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;   

int N , M , H , K ;
int S , T , P;
int pass_corp[256],pass_cost[256];
int dp[256];
int min_cost[128][32];

struct Edge { int to , cost , time , corp ;}; 
vector < Edge > edge[128];


void init(){
  rep(i,128)edge[i].clear();
  rep(i,256)pass_corp[i] = 0;
  rep(i,256)dp[i] = INF;
}

int dijkstra(int pass){

  priority_queue < Pii ,vector < Pii > ,greater < Pii > > que;
  // cost, time , v
  que.push(make_pair(dp[pass],make_pair(0,S)));
  rep(i,128)rep(j,32)min_cost[i][j] = INF;

  while(!que.empty()){
    Pii tp = que.top();que.pop();
    int cost = tp.fr , time = tp.sc.fr , v = tp.sc.sc;
    if(v == T)return cost;
    rep(i,sz(edge[v])){
      Edge e = edge[v][i];
      int n_time = time + e.time;
      if(n_time > H)continue;
      int n_cost = (pass & (1 << e.corp)) ? cost : cost + e.cost;
      if(n_cost < min_cost[e.to][n_time]){
	min_cost[e.to][n_time] = n_cost;
	que.push(make_pair(n_cost,make_pair(n_time,e.to)));
      }      
    }
  }
  return INF;
}


void mk_table(){
  int ret = INF ;
  dp[0] = 0;
  rep(i,1<<K){
    if(dp[i] != INF){
      rep(j,P){
	dp[i|pass_corp[j]] = min(dp[i|pass_corp[j]],dp[i]+pass_cost[pass_corp[j]]);
      }
    }
  }
  return ;
}

int main(void){
  while(cin >> N >> M >> H >> K &&N){
    init();
    rep(i,M){
      int a , b , cost , time , corp;
      cin >> a >> b >> cost >> time >> corp;      
      a-- , b-- , corp--;
      edge[a].push_back((Edge){b,cost,time,corp});
      edge[b].push_back((Edge){a,cost,time,corp});
    }

    cin >> S >> T ;
    cin >> P;
    S--,T--;
    rep(i,P){
      int corp_num , corp_cost;
      cin >> corp_num >> corp_cost;
      rep(j,corp_num){
	int corp;
	cin >> corp; corp--;
	pass_corp[i] |= 1 << corp;
      }
      pass_cost[pass_corp[i]] = corp_cost;
    }

    mk_table();

    int ret = INF;
    rep(i,1<<K)if(dp[i] != INF)ret = min(ret,dijkstra(i));
    if(ret != INF)cout << ret << endl;
    else cout << -1 << endl;
  }
  return 0;
}