jiry_2's Blog

把原图复制K+1遍，如果原来点I，J之间有边就在第P层的I向P+1层J连一条有向边，同理，第P层的点J向P+1层I连一条有向边。以第一层S为原点做最短路，答案就是所有层T点距离的最小值。应注意SPFA会T，应该用DJ+HEAP。

program p2736;
	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..3000000] 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);
		readln(s,t);
		inc(s); inc(t);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to m do begin
			readln(k1,k2,k3);
			inc(k1); inc(k2);
			add(k1,k2,k3);
			for j:=0 to k-1 do begin
				ade(j*n+k1,j*n+n+k2,0);
				ade(j*n+k2,j*n+k1+n,0);
				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;
		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.