UVa 590

being similar to TSP and shortest path problem
state:
    dp[i][j] - minimum cost at city j on day i
transition:
    dp[i][j]=min(dp[i-1][k]+f[k->j][i]), all k!=j and k->j refers to flight cost index
    the first tricky thing is to set d[i][j]=-1 if it can't be reached
    second one is how to calculate flight cost index
    flight's index from k->j is (k-1)*(n-1)+j, then minus 1 if k<j
    and flight cost's index on day i is i%d, or it's d if i%d==0

/* UVas */
/*****************************************************************************/
int n, k, c=1;
int f[91][31];
int d[1001][11];
int main(void) {
    while (cin>>n>>k&&n&&k) {
        for (int i=1; i<=n*(n-1); i++) {
            cin>>f[i][0];
            for (int j=1; j<=f[i][0]; j++) {
                cin>>f[i][j];
            }
        }
        memset(d, -1, sizeof(d));
        for (int i=2; i<=n; i++) {
            d[1][i]=f[i-1][1]==0?-1:f[i-1][1];
        }
        for (int i=2; i<=k; i++) {
            for (int j=1; j<=n; j++) {
                for (int l=1; l<=n; l++) {
                    if (l==j||d[i-1][l]==-1) {
                        continue;
                    }
                    int a=(l-1)*(n-1)+j;
                    a=l<j?a-1:a;
                    int b=i%f[a][0]==0?f[a][0]:i%f[a][0];
                    if (!f[a][b]) {
                        continue;
                    }
                    if (d[i-1][l]+f[a][b]<d[i][j]||d[i][j]==-1) {
                        d[i][j]=d[i-1][l]+f[a][b];
                    }
                }
            }
        }
        cout<<"Scenario #"<<c<<endl;
        d[k][n]==-1?cout<<"No flight possible.":cout<<"The best flight costs "<<d[k][n]<<".";
        cout<<endl<<endl;
        c++;
    }
    return 0;
}
/*****************************************************************************/