1820: [JSOI2010]Express Service 快递服务
1820: [JSOI2010]Express Service 快递服务
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 847 Solved: 325
[Submit][Status]
Description
Input
Output
Sample Input
0 5 0 6
6 0 5 6
1 6 0 6
1 1 1 0
1 1 1 1 4 4 2 2 2 3
Sample Output
样例说明:到每个请求收件地点的司机分别为1 1 1 1 3 3 2 2 2 1,因此司机1只需从起使点1移动到地点3,司机2只需停留在地点2,司机3从起始点3移动到地点4。
HINT
Source
题解:b数组的第一个参数表示寄件的个数,另外两人就是第二第三个参数的最短路径,这样子Dp下去,不难转移(Ps:类比背包九讲里面压缩空间的方法,这里面dp时还是最好采取交替使用两个数组的方法——本程序里面分别为b[1]和b[0])
1 var 2 i,j,k,l,m,n,p,t,ans:longint; 3 c:array[0..250,0..250] of longint; 4 b:array[0..4,0..250,0..250] of longint; 5 a:array[0..2000] of longint; 6 function min(x,y:longint):longint;inline; 7 begin 8 if x<y then min:=x else min:=y; 9 end; 10 begin 11 readln(n); 12 for i:=1 to n do 13 begin 14 for j:=1 to n do 15 read(c[i,j]); 16 readln; 17 end; 18 fillchar(b,sizeof(b),127); 19 b[0,2,3]:=0; 20 b[0,3,2]:=0; 21 a[0]:=1; 22 p:=1; 23 t:=1; 24 while not(eoln) do 25 begin 26 read(a[t]); 27 fillchar(b[p],sizeof(b[p]),127); 28 for i:=1 to n do 29 for j:=1 to n do 30 begin 31 b[p,i,j]:=min(b[p,i,j],b[1-p,i,j]+c[a[t-1],a[t]]); 32 b[p,a[t-1],j]:=min(b[p,a[t-1],j],b[1-p,i,j]+c[i,a[t]]); 33 b[p,a[t-1],i]:=min(b[p,a[t-1],i],b[1-p,i,j]+c[j,a[t]]); 34 end; 35 p:=1-p; 36 inc(t); 37 end; 38 readln; 39 ans:=maxlongint; 40 for i:=1 to n do 41 for j:=1 to n do 42 ans:=min(ans,b[1-p,i,j]); 43 writeln(ans); 44 readln; 45 end. 46
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。