#include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,n) for(int i=0,i##_end=(n);i&price , vector >&route, vector&itinerary , int n , vector&ticket) { int m=(int)itinerary.size(); itinerary.push_back(-1); // typedef pair > > > data_t ; priority_queue< data_t,vector , greater >qu; int val=-1; map,pair > memo; qu.push(MP(0,MP(1,MP(itinerary[0],MP(-1,-1))))); while(!qu.empty()) { int cost=qu.top().first; int step=qu.top().second.first; int pos =qu.top().second.second.first; int tic =qu.top().second.second.second.first; int pstep =qu.top().second.second.second.second; qu.pop(); if(memo.find(MP(step,pos))!=memo.end()) continue; memo[MP(step,pos)]=MP(pstep,tic); if(step==m && pos==itinerary[m-1]){ val = cost ; break; } FOR(i,n) { if(route[i][0]!=pos) continue; int st=step; FOR(j,route[i].size()) { if(itinerary[st]==route[i][j]) st++; qu.push(MP(cost+price[i],MP(st,MP(route[i][j],MP(i,step))))); } } } { pair now(m,itinerary[m-1]),next; ticket.clear(); while(1){ if(memo.find(now) == memo.end()) abort(); pair pre = memo[now]; int ti = pre.second; if(ti == -1) break; ticket.push_back(ti+1); now = MP(pre.first,route[ti].front()); } reverse(ticket.begin(),ticket.end()); } return val; } int main(){ int n,case_no=1; while(cin>>n&&n) { vector price(n); vector > route(n); FOR(i,n){ cin>>price[i]; int t; cin>>t; FOR(_,t){ int x; cin>>x; route[i].push_back(x-1); } } int m; cin >> m; FOR(i,m){ int t; cin >> t; vector itinerary (t); FOR(j,t) { cin>>itinerary[j]; itinerary[j]--; } int ans = 0; vector ticket; ans = solve(price, route , itinerary , n , ticket); printf("Case %d, Trip %d: Cost = %d\n", case_no, i+1 , ans); printf(" Tickets used:"); FOR(j,ticket.size()) printf(" %d" , ticket[j]); puts(""); } case_no++; } return 0; }