SPOJ - SERVICE

Problem Statement:
SPOJ - Mobile Service (SERVICE)

Summary:
A company has 3 staffs which are initially located at town 1, 2, and 3. There are M <= 200 towns and N <= 1000 requests. Each request is located at a particular town, and a staff has to move to that town to deliver the service. The requests are sequentially serviced. Staffs cannot move to a town without an accompanying request, and no staff can be in the same town at the same time. Given a table of costs of travel between towns, find the minimum cost needed to service all requests.



Solution:
The DP technique to solve this problem requires an important observation, that is, after servicing request i, you will have a staff located at town i. This means that instead of having 4 parameters to take care of (location of staff 1, staff 2, staff 3, and next town to service), we just need 3 parameters (location staff 1, staff 2, and next town to service) since the location of the last staff is determinable from the town that has just been serviced. As such we can have a \(O(NM^2)\) running time, where N is number of requests and M is number of town. This is actually still very slow, but it cut the time limit on SPOJ :).

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

/*
S(a, b, i) = cost to handle request [i+1 .. N] with a, b, and item[i]
O(N*M*M)
*/
int INF = (int) 1e8;
int dp[203][203][2];
int cost[203][203];
int town[1003];
int N, M;

void solve() {
    int s = (N-2)%2;
    for(int i=0;i<M;++i){
        for(int j=0;j<M;++j){
            dp[i][j][s] = INF;
            if(i == j || i == town[N-2] || j==town[N-2]) {
                continue;
            }
            if(j!=town[N-1] && town[N-2]!=town[N-1]) dp[i][j][s] = cost[i][town[N-1]];
            if(i!=town[N-1] && town[N-2]!=town[N-1]) dp[i][j][s] = min(dp[i][j][s], cost[j][town[N-1]]);
            if(i!=town[N-1] && j!=town[N-1]) dp[i][j][s] = min(dp[i][j][s], cost[town[N-2]][town[N-1]]);
        }
    }
    for(int k=N-3;k>=0;--k){
        int cur = k%2;
        for(int i=0;i<M;++i){
            for(int j=0;j<M;++j){
                if(i==j || i == town[k] || j == town[k]){
                    dp[i][j][cur] = INF;
                    continue;
                }
                dp[i][j][cur] = min(cost[i][town[k+1]] + dp[j][town[k]][cur^1], min(cost[j][town[k+1]] + dp[i][town[k]][cur^1], cost[town[k]][town[k+1]] + dp[i][j][cur^1]));
            }
        }
    }
    int ans = min(cost[0][town[0]] + dp[1][2][0], min(cost[1][town[0]] + dp[0][2][0], cost[2][town[0]] + dp[0][1][0]));
    printf("%d\n", ans);
}


int main(){
    int tc;
    cin >> tc;
    while(tc--){
        scanf("%d %d", &M, &N);
        for(int i=0;i<M;++i){
            for(int j=0;j<M;++j){
                scanf("%d", &cost[i][j]);
            }
        }
        for(int i=0;i<N;++i){
            scanf("%d", &town[i]);
            --town[i];
        }
        solve();
    }
    return 0;
}