[HOJ] 216 - 快遞服務

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int s[205][205],dp[205][205],dp2[205][205];
int main(){
    int n,i,j,x,y,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&s[i][j]);
    scanf("%d",&x);
    memset(dp2,-1,sizeof(dp2));
    dp2[2][3]=dp2[3][2]=s[1][x];
    dp2[1][3]=dp2[3][1]=s[2][x];
    dp2[2][1]=dp2[1][2]=s[3][x];
    y=x;
    while(scanf("%d",&x)!=EOF){
        if(x==y) continue;
        memset(dp,-1,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++){
                if(dp2[i][j]!=-1){
                    if(dp[i][j]==-1 || dp2[i][j]+s[y][x]<dp[i][j])
                        dp[i][j]=dp[j][i]=dp2[i][j]+s[y][x];
                    if(dp[i][y]==-1 || dp2[i][j]+s[j][x]<dp[i][y])
                        dp[i][y]=dp[y][i]=dp2[i][j]+s[j][x];
                    if(dp[y][j]==-1 || dp2[i][j]+s[i][x]<dp[y][j])
                        dp[y][j]=dp[j][y]=dp2[i][j]+s[i][x];
                }
            }
        y=x;
        memcpy(dp2,dp,sizeof(dp));
    }
    ans=999999999;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(dp[i][j]!=-1)
                ans=min(ans,dp[i][j]);
    printf("%d\n",ans);
}