jiry_2's Blog

类似于2763，不过层与层之间的边权要改为原边权的一半。我直接改了这个细节贴2763的代码了。

program p2662;
	type
		bian=record
			next,point,w:longint;
		end;
		heap=record
			dis,point:longint;
		end;
	var
		p,d:array[1..200000] of longint;
		x:array[1..200000] of heap;
		b:array[1..1500000] of bian;
		ans,len,s,t,n,m,k,i,j,k1,k2,k3,maxn:longint;
		now:heap;
	procedure ade(k1,k2,k3:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].w:=k3;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure add(k1,k2,k3:longint);
		begin
			ade(k1,k2,k3);
			ade(k2,k1,k3);
		end;
	function minn(k1,k2:longint):longint;
		begin
			if x[k1].dis<=x[k2].dis then exit(k1) else exit(k2);
		end;
	function min(k1,k2,k3:longint):longint;
		begin
			exit(minn(k1,minn(k2,k3)));
		end;
	procedure press(k:longint);
		var
			i:longint;
			j:heap;
		begin
			i:=min(k,k*2,k*2+1);
			if i=k then exit;
			j:=x[k]; x[k]:=x[i]; x[i]:=j;
			press(i);
		end;
	procedure find(k:longint);
		var
			i:heap;
		begin
                        if k=1 then exit;
			if x[k].dis<x[k div 2].dis then begin
				i:=x[k];
				x[k]:=x[k div 2];
				x[k div 2]:=i;
				find(k div 2);
			end;
		end;
	procedure push(k:heap);
		var
			i,j:longint;
		begin
			i:=p[k.point];
			while i<>0 do begin
				j:=b[i].point;
				if k.dis+b[i].w<d[j] then begin
					d[j]:=k.dis+b[i].w;
					inc(len);
					x[len].point:=j;
					x[len].dis:=d[j];
					find(len);
				end;
				i:=b[i].next;
			end;
		end;
	begin
		readln(n,m,k);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			add(k1,k2,k3);
			for j:=0 to k-1 do begin
				ade(j*n+k1,j*n+n+k2,k3 div 2);
				ade(j*n+k2,j*n+k1+n,k3 div 2);
				add(j*n+n+k1,j*n+n+k2,k3);
			end;
		end;
		fillchar(d,sizeof(d),$3f);
		fillchar(x,sizeof(x),$7f);
		maxn:=x[1].dis;
		s:=1; t:=n;
		len:=1; x[1].point:=s; d[s]:=0; x[1].dis:=0;
		while len>0 do begin
			dec(len);
			now:=x[1];
			if len>0 then begin
				x[1]:=x[len+1];
				x[len+1].dis:=maxn;
				press(1);
			end;
			push(now);
		end;
		ans:=maxlongint;
		for i:=0 to k do
			if d[i*n+t]<ans then ans:=d[i*n+t];
		writeln(ans);
	end.