[UVA] 1048 - Low Cost Air Travel

#include<stdio.h>
#include<string.h>
#include<vector>
#include<map>
#define inf 1<<30
using namespace std;
struct P{
    int a,b;
}p[25][205],in;
int dis[25][205],is[25][205],city[25][205],use[25][205],price[25],arr[25];
vector<int> ticket[25],ans;
map<int,int> ma;
int main(){
    int n,m,t,x,y,z,i,j,k,r,add,cnt,cnt1=0,cnt2;
    while(scanf("%d",&n)!=EOF && n){
        memset(ticket,0,sizeof(ticket));
        ma.clear();
        cnt=0;
        for(i=0;i<n;i++){
            scanf("%d",&price[i]);
            scanf("%d",&m);
            for(j=0;j<m;j++){
                scanf("%d",&x);
                if(ma.find(x)==ma.end())
                    ma[x]=cnt++;
                ticket[i].push_back(ma[x]);
            }
        }
        scanf("%d",&t);
        cnt2=0,cnt1++;
        while(t--){
            scanf("%d",&m);
            for(i=0;i<m;i++){
                scanf("%d",&arr[i]);
                arr[i]=ma[arr[i]];
            }
            memset(is,0,sizeof(is));
            memset(city,0,sizeof(city));
            memset(p,-1,sizeof(p));
            for(i=0;i<=m;i++)
                for(j=0;j<=cnt;j++)
                    dis[i][j]=inf,p[i][j]=(P){-1,-1};
            dis[0][arr[0]]=0;
            for(i=0;i<m;i++){
                while(1){
                    z=inf,y=inf;
                    for(j=0;j<=cnt;j++)
                        if(dis[i][j]<z && is[i][j]==0)
                            z=dis[i][j],x=j,y=city[i][j];
                    if(z==inf) break;
                    is[i][x]=1;
                    for(j=0;j<n;j++){
                        if(ticket[j][0]!=x) continue;
                        add=i;
                        for(k=1;k<ticket[j].size();k++){
                            if(add+1<m && arr[add+1]==ticket[j][k]) add++;
                            if(dis[i][x]+price[j]<dis[add][ticket[j][k]]){
                                dis[add][ticket[j][k]]=dis[i][x]+price[j];
                                p[add][ticket[j][k]].a=i;
                                p[add][ticket[j][k]].b=x;
                                use[add][ticket[j][k]]=j;
                                city[add][ticket[j][k]]=city[i][x]+1;
                            }
                        }
                    }
                }
            }
            z=inf,x=inf;
            for(i=0;i<cnt;i++)
                if(dis[m-1][i]<z)
                    z=dis[m-1][i],x=city[m-1][i],y=i;
            x=m-1;
            printf("Case %d, Trip %d: Cost = %d\n  Tickets used:",cnt1,++cnt2,z);
            ans.clear();
            while(x>=0 && y>=0){
                ans.push_back(use[x][y]);
                k=p[x][y].a;
                y=p[x][y].b;
                x=k;
            }
            for(i=ans.size()-2;i>=0;i--)
                printf(" %d",ans[i]+1);
            puts("");
        }
    }
}