貌似被卡常数了？
还是DP可以优化？
program p644;
var
k,tot,x,b,c,minn,i,j,n,t:longint;
a1,a2,a3:array[0..17,0..17]of longint;
time,w:array[0..1001]of longint;
f:array[0..1001,0..17,0..17,0..17]of longint;
procedure init;
begin
assign(input,'p644.in');
reset(input);
assign(output,'p644.out');
rewrite(output);
end;
procedure outit;
begin
close(input);
close(output);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;
procedure qsort(l,r:longint);
var
i,j,x,t:longint;
begin
i:=l; j:=r; x:=time[(l+r)div 2];
repeat
while time[i]<x do inc(i);
while time[j]>x do dec(j);
if not(i>j) then
begin
t:=time[i]; time[i]:=time[j]; time[j]:=t;
t:=w[i]; w[i]:=w[j]; w[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure main;
begin
readln(n);
for i:=1 to n do readln(time[i],w[i]);
qsort(1,n);
for i:=1 to 16 do
for j:=1 to 16 do read(a1[i,j]);
for i:=1 to 16 do
for j:=1 to 16 do read(a2[i,j]);
for i:=1 to 16 do
for j:=1 to 16 do read(a3[i,j]);
fillchar(f,sizeof(f),$7);
f[0,1,1,1]:=0;
for i:=1 to n do
for b:=1 to 16 do
for c:=1 to 16 do
for x:=1 to 16 do
begin
f[i,w[i],b,c]:=min(f[i,w[i],b,c],f[i-1,x,b,c]+a1[x,w[i]]);
f[i,b,w[i],c]:=min(f[i,b,w[i],c],f[i-1,b,x,c]+a2[x,w[i]]);
f[i,c,b,w[i]]:=min(f[i,c,b,w[i]],f[i-1,c,b,x]+a3[x,w[i]]);
end;
minn:=maxlongint;
for b:=1 to 16 do
for c:=1 to 16 do minn:=min(minn,f[n,w[n],b,c]);
for b:=1 to 16 do
for c:=1 to 16 do minn:=min(minn,f[n,b,w[n],c]);
for b:=1 to 16 do
for c:=1 to 16 do minn:=min(minn,f[n,c,b,w[n]]);
writeln(minn);
end;
begin
init;
readln(tot);
for k:=1 to tot do main;
outit;
end.
得分： 100分 [我要评价一下题目~]
提交日期： 2011-9-27 21:37:00
有效耗时： 3484毫秒
测试结果1: 通过本测试点|有效耗时297ms
测试结果2: 通过本测试点|有效耗时250ms
测试结果3: 通过本测试点|有效耗时234ms
测试结果4: 通过本测试点|有效耗时266ms
测试结果5: 通过本测试点|有效耗时297ms
测试结果6: 通过本测试点|有效耗时328ms
测试结果7: 通过本测试点|有效耗时437ms
测试结果8: 通过本测试点|有效耗时500ms
测试结果9: 通过本测试点|有效耗时438ms
测试结果10: 通过本测试点|有效耗时437ms
提交代码： view sourceprint?01.var i,j,k,l,n,t,q,max:longint;
02.
d:array[1..1000,1..16,1..16,1..16]of longint;
03.
a,b:array[1..1000]of longint;
04.
f1,f2,f3:array[1..16,1..16]of integer;
05.function min(a,b:longint):longint;
06.begin
07.if a<b then exit(a)
08.
else exit(b);
09.end;
10.procedure kp(l,r:longint);
11.var
12.
ii,jj,kk,nn,mm,tt:longint;
13.begin
14.
ii:=l;
15.
jj:=r;
16.
nn:=(l+r) div 2;
17.
mm:=a[nn];
18.
while ii<jj do
19.
begin
20.
while a[ii]<mm do inc(ii);
21.
while a[jj]>mm do dec(jj);
22.
if ii<=jj then
23.
begin
24.
tt:=a[ii];
25.
a[ii]:=a[jj];
26.
a[jj]:=tt;
27.
tt:=b[ii];
28.
b[ii]:=b[jj];
29.
b[jj]:=tt;
30.
inc(ii);
31.
dec(jj);
32.
end;
33.
end;
34.
if jj>l then kp(l,jj);
35.
if ii<r then kp(ii,r);
36.end;
37.begin
38.readln(t);
39.for q:=1 to t do begin
40.readln(n);
41.for i:=1 to n do
42.readln(a[i],b[i]);
43.kp(1,n);
44.for i:=1 to 16 do
45.for j:=1 to 16 do
46.read(f1[i,j]);
47.for i:=1 to 16 do
48.for j:=1 to 16 do
49.read(f2[i,j]);
50.for i:=1 to 16 do
51.for j:=1 to 16 do
52.read(f3[i,j]);
53.filldword(d,sizeof(d)div 4,maxlongint div 2);
54.d[1,b[1],1,1]:=f1[1,b[1]];
55.d[1,1,b[1],1]:=f2[1,b[1]];
56.d[1,1,1,b[1]]:=f3[1,b[1]];
57.for i:=2 to n do
58.for j:=1 to 16 do
59.for k:=1 to 16 do begin
60.d[i,b[i],j,k]:=min(d[i,b[i],j,k],d[i-1,b[i-1],j,k]+f1[b[i-1],b[i]]);
61.d[i,j,b[i],k]:=min(d[i,j,b[i],k],d[i-1,j,b[i-1],k]+f2[b[i-1],b[i]]);
62.d[i,j,k,b[i]]:=min(d[i,j,k,b[i]],d[i-1,j,k,b[i-1]]+f3[b[i-1],b[i]]);
63.d[i,b[i],b[i-1],k]:=min(d[i,b[i],b[i-1],k],d[i-1,j,b[i-1],k]+f1[j,b[i]]);
64.d[i,b[i],k,b[i-1]]:=min(d[i,b[i],k,b[i-1]],d[i-1,j,k,b[i-1]]+f1[j,b[i]]);
65.d[i,j,b[i],b[i-1]]:=min(d[i,j,b[i],b[i-1]],d[i-1,j,k,b[i-1]]+f2[k,b[i]]);
66.d[i,b[i-1],b[i],k]:=min(d[i,b[i-1],b[i],k],d[i-1,b[i-1],j,k]+f2[j,b[i]]);
67.d[i,j,b[i-1],b[i]]:=min(d[i,j,b[i-1],b[i]],d[i-1,j,b[i-1],k]+f3[k,b[i]]);
68.d[i,b[i-1],j,b[i]]:=min(d[i,b[i-1],j,b[i]],d[i-1,b[i-1],j,k]+f3[k,b[i]]);
69.end;
70.max:=maxlongint;
71.for j:=1 to 16 do
72.for k:=1 to 16 do begin
73.if d[n,j,k,b[n]]<max then max:=d[n,j,k,b[n]];
74.if d[n,j,b[n],k]<max then max:=d[n,j,b[n],k];
75.if d[n,b[n],j,k]<max then max:=d[n,b[n],j,k];
76.end;
77.writeln(max);
78.end;
79.end.