jiry_2's Blog

以天为状态，则f[i]=min(dj[1,i]*i,dj[j,i]*(i-j+1)+k+f[j-1](2<=j<=i))，dj[i,j]表示第i天到第j天均走同样的路线时的最短路。不需要初始化，在过程中要用到位运算来降低时间复杂度，详细见代码。

program p1003;
	type
		bian=record
			next,point,w:longint;
		end;
	var
		b:array[1..1000000] of bian;
		p,two,d:array[1..30] of longint;
		x,f:array[0..200] of int64;
		len,i,j,n,m,k,e,q,k1,k2,k3,maxn:longint;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			b[len].w:=k3;
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function min(k1,k2:int64):int64;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function findmin:longint;
		var
			i,j,k:longint;
		begin
			k:=maxlongint; j:=0;
			for i:=1 to m do
				if (d[i]<k) and (d[i]<>-1) then begin
					k:=d[i];
					j:=i;
				end;
			exit(j);
		end;
	procedure push(k1,k2:longint);
		var
			i,j:longint;
		begin
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				if (b[i].w+d[k1]<d[j]) and (k2 and two[j]=0) then 
					d[j]:=b[i].w+d[k1];
				i:=b[i].next;
			end;
			d[k1]:=-1;
		end;
	function dj(k:longint):longint;
		var
			i,j,now:longint;
		begin
			fillchar(d,sizeof(d),$3f);
			d[1]:=0;
			for i:=1 to m do begin
				now:=findmin;
				if now=m then exit(d[m]);
				push(now,k);
			end;
		end;
	begin
		readln(n,m,k,e);
		len:=0;
		fillchar(b,sizeof(b),0);
		fillchar(p,sizeof(p),0);
		for i:=1 to e do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
		end;
		two[1]:=1;
		for i:=2 to m do
			two[i]:=two[i-1]*2;
		readln(q);
		fillchar(x,sizeof(x),0);
		for i:=1 to q do begin
			readln(k1,k2,k3);
			for j:=k2 to k3 do
				x[j]:=x[j] or two[k1];
		end;
		fillchar(f,sizeof(f),$3f);
		maxn:=f[1];
		f[0]:=0;
		for i:=1 to n do begin
			k1:=x[i];
			for j:=i downto 2 do begin
				k2:=dj(k1);
				if k2<>maxn then begin
					f[i]:=min(f[i],k2*(i-j+1)+k+f[j-1]);
					k1:=k1 or x[j-1];
				end else break;
			end;
			k2:=dj(k1);
			if k2<>maxn then f[i]:=min(f[i],k2*i);
		end;
		writeln(f[n]);
	end.