UVa 10702

again and again a simple and easy dp
state:
    dp[i][j] - max profit when in city j at day i
transition:
    dp[i][j]=max(dp[i][j], dp[i-1][k]+l[k][j]), 1<=k<=C
    for all city k, if he was at city k yesterday, then we must have got the max profit of
    dp[i-1][k], and then we add l[k][j] to the sum

/* UVas */
/*****************************************************************************/
int C, S, E, T;
int e[101];
int l[101][101];
int d[1001][101];
int main(void) {
    while (cin>>C>>S>>E>>T&&C&&S&&E&&T) {
        for (int i=1; i<=C; i++) {
            for (int j=1; j<=C; j++) {
                cin>>l[i][j];
            }
        }
        for (int i=1; i<=E; i++) {
            cin>>e[i];
        }
        memset(d, -1, sizeof(d));
        d[0][S]=0;
        for (int i=1; i<=T; i++) {
            for (int j=1; j<=C; j++) {
                for (int k=1; k<=C; k++) {
                    if (d[i-1][k]!=-1) {
                        d[i][j]=max(d[i][j], d[i-1][k]+l[k][j]);
                    }
                }
            }
        }
        int r=0;
        for (int i=1; i<=E; i++) {
            r=max(r, d[T][e[i]]);
        }
        cout<<r<<endl;
    }
    return 0;
}
/*****************************************************************************/