比不上Seter28行写完NOI海拔啊,Pascal就这样子...还有压行也挺蛋疼的这次是例外我的代码风格没这么蛋疼.算法 :: ZKW线段树作为优先队列的使用,速度比堆Dijkstra稍微慢一点点(2秒和2010ms的区别). 不过代码短很多呢,主要是为了写Dijkstra的费用流准备.
简直不能看,还有可能有错这JB压行根本不能调试
{$INLINE_ON}_program_Dijkstra_1;
type_tnode=record_n,w,next:longint;_end;
const_maxn=100017;_maxm=1000017;_maxint=longint($3f3f3f3f);
var_g,d:array[0..maxn]_of_longint;
____v:array[0..maxn]_of_boolean;
____t:array[0..maxn*4]_of_longint;
____mem:array[0..maxm]_of_tnode;
____n,m,memsize,zkw:longint;
function_min(i,j:longint):longint;_inline;_begin_if_i<j_then_exit(i)_else_exit(j);__end;
function_max(i,j:longint):longint;_inline;_begin_if_i>j_then_exit(i)_else_exit(j);__end;
procedure_insnbs(u,v,iw:longint);_inline;_begin_inc(memsize);_with_mem[memsize]_do_begin
________n:=v;_w:=iw;_next:=g[u];_end;_g[u]:=memsize;_end;
procedure_edit(i,j:longint);_inline;____________________________________________________begin
inc(i,zkw);_t[i]:=j;_while_i>0_do_begin_j:=i>>1;_t[j]:=min(t[i],t[i_xor_1]);_i:=j;_end;_end;
procedure_sssp(u:longint);
var_i,j,k,t1:longint;
begin
zkw:=1;_while_zkw<n+2_do_zkw:=zkw<<1;_fillchar(t,sizeof(t),0);_edit(u,0);_for_i:=1_to_n_do_begin
________j:=1;_while_j<zkw_do_begin_k:=j<<1;_j:=k+byte(t[k+1]<t[k]);_end;_d[j-zkw]:=t[j];
________dec(j,zkw);_edit(j,maxint);v[j]:=true;_t1:=g[j];_while_t1<>0_do_begin
________________if_(t[mem[t1].n+zkw]>t[j]+mem[t1].w)_then_edit(mem[t1].n,d[j]+mem[t1].w);_t1:=mem[t1].next;
________end;
end;_end;_procedure_init;
var_i,j,k,u,v,w:longint;
begin
fillchar(g,sizeof(g),0);_memsize:=0;_readln(n,m);_for_i:=1_to_m_do_begin_readln(u,v,w);_insnbs(u,v,w);_end;
end;_begin
init;_sssp(1);
end.