讨论 / 纠结了半天,AC了,发个代码把。。。
lx99410 2011-10-04 13:10:00
点我顶贴 收藏 删除
#include<stdio.h>

#include<algorithm>

using namespace std;

const int maxn=1001;

const int maxp=17;

const int INF=838860;

struct node{int a,b;}ico[maxn];

int d[maxn][maxp][maxp][maxp],v[4][maxp][maxp],N,ans;

inline bool cmp(struct node x,struct node y){return x.a<y.a;}

inline int getint(){

int d=0,flag=0; char ch=' ';

while(!isdigit(ch=getchar()))if(ch=='-')break;

if(ch=='-')flag=1;else d=ch-48;

while(isdigit(ch=getchar()))d=d*10+ch-48;

if(flag)return -d;else return d;

}

int main(){int tot;scanf("%d",&tot);

while(tot--){

N=getint();ans=(1<<31)-1;

for(int i=1;i<=N;i++)ico[i].a=getint(),ico[i].b=getint();

sort(ico+1,ico+1+N,cmp);

for(int i=1;i<=16;i++)

for(int j=1;j<=16;j++){

v[1][i][j]=getint();

for(int k=1;k<=16;k++)

for(int m=1;m<=N;m++)

d[m][i][j][k]=INF;

}

for(int i=1;i<=16;i++)

for(int j=1;j<=16;j++)

v[2][i][j]=getint();

for(int i=1;i<=16;i++)

for(int j=1;j<=16;j++)

v[3][i][j]=getint();

d[1][ico[1].b][1][1]=v[1][1][ico[1].b];

d[1][1][ico[1].b][1]=v[2][1][ico[1].b];

d[1][1][1][ico[1].b]=v[3][1][ico[1].b];

for(int i=2;i<=N;i++)

for(int j=1;j<=16;j++)

for(int k=1;k<=16;k++){

d[i][ico[i].b][j][k]=min(d[i][ico[i].b][j][k],d[i-1][ico[i-1].b][j][k]+v[1][ico[i-1].b][ico[i].b]);

d[i][j][ico[i].b][k]=min(d[i][j][ico[i].b][k],d[i-1][j][ico[i-1].b][k]+v[2][ico[i-1].b][ico[i].b]);

d[i][j][k][ico[i].b]=min(d[i][j][k][ico[i].b],d[i-1][j][k][ico[i-1].b]+v[3][ico[i-1].b][ico[i].b]);

d[i][ico[i].b][ico[i-1].b][k]=min(d[i][ico[i].b][ico[i-1].b][k],d[i-1][j][ico[i-1].b][k]+v[1][j][ico[i].b]);

d[i][ico[i].b][k][ico[i-1].b]=min(d[i][ico[i].b][k][ico[i-1].b],d[i-1][j][k][ico[i-1].b]+v[1][j][ico[i].b]);

d[i][j][ico[i].b][ico[i-1].b]=min(d[i][j][ico[i].b][ico[i-1].b],d[i-1][j][k][ico[i-1].b]+v[2][k][ico[i].b]);

d[i][ico[i-1].b][ico[i].b][k]=min(d[i][ico[i-1].b][ico[i].b][k],d[i-1][ico[i-1].b][j][k]+v[2][j][ico[i].b]);

d[i][j][ico[i-1].b][ico[i].b]=min(d[i][j][ico[i-1].b][ico[i].b],d[i-1][j][ico[i-1].b][k]+v[3][k][ico[i].b]);

d[i][ico[i-1].b][j][ico[i].b]=min(d[i][ico[i-1].b][j][ico[i].b],d[i-1][ico[i-1].b][j][k]+v[3][k][ico[i].b]);

}

for(int j=1;j<=16;j++)

for(int k=1;k<=16;k++){

if(d[N][j][k][ico[N].b]<ans)ans=d[N][j][k][ico[N].b];

if(d[N][j][ico[N].b][k]<ans)ans=d[N][j][ico[N].b][k];

if(d[N][ico[N].b][j][k]<ans)ans=d[N][ico[N].b][j][k];

}

printf("%d\n",ans);

}

return 0;

}

查看更多回复
提交回复