TIOJ 1144 5.快遞服務 [95 全國賽]

poao899    1144    Accepted    496K    591MS    G++    1.12K    2010-04-01 16:06:45                          .








狀態   O(n^3 m ) *   轉移  O(     1    )      ==>      狀態   O(n^2 m ) *   轉移  O(     1    ) 


然後就可以過了ˊˇˋ



每個狀態一定要有一個司機在上一個點上嘛ˇ












//*************************************

#include<stdio.h>
#define INF 1000000000
struct dp{
    int a[210][210];
}d1, d2, *now, *pre, *tmp;
int m, dist[210][210], n, pn;
int main(){
    now=&d1, pre=&d2;
    scanf("%d", &m);
    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++){
            scanf("%d", &dist[i][j]);
            now->a[i][j]= pre->a[i][j]= INF;
        }
    for(int i=0;;i++){
        if(scanf("%d", &n)==EOF)break;
        --n;
        if(i==0){
            now->a[0][1]= dist[2][n];
            now->a[1][2]= dist[0][n];
            now->a[0][2]= dist[1][n];
        }else{
            for(int j=0; j<m; j++)
                for(int k=0; k<m; k++)
                    if(pre->a[j][k]!= INF){
                        if(now->a[j][k]> pre->a[j][k]+ dist[pn][n])now->a[j][k]= pre->a[j][k]+ dist[pn][n];
                        if(now->a[pn][k]> pre->a[j][k]+ dist[j][n])now->a[pn][k]= pre->a[j][k]+ dist[j][n];
                        if(now->a[pn][j]> pre->a[j][k]+ dist[k][n])now->a[pn][j]= pre->a[j][k]+ dist[k][n];
                        pre->a[j][k]= INF;
                    }
        }
        tmp=pre; pre=now; now=tmp; pn=n;
    }
    int min =INF;
    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++)
            if(pre->a[i][j]< min)
                min= pre->a[i][j];
    printf("%d\n", min);
}