program s1;
var a:array[0..1000,0..1000]of longint;
zheng,fan,v:array[1..1000]of longint;
i,j,k,l,n,m,o,p:longint;
function min(a,b:longint):longint;
begin
if a< b then exit(a)
else exit(b);
end;
procedure spfa;
var t:array[1..1000000]of longint;
b:array[1..1000]of boolean;
i,j,k,tou,wei:longint;
begin
fillchar(b,sizeof(b),true);
b[1]:=false; t[1]:=1;
zheng:=v;
tou:=1;wei:=1;
while tou<=wei do
begin
if tou>100000 then break;
k:=t[tou];
for i:=1 to a[k,0] do
begin
if zheng[a[k,i]]>min(v[a[k,i]],zheng[k]) then zheng[a[k,i]]:=min(zheng[k],v[a[k,i]]);
if b[a[k,i]] then
begin
inc(wei);
t[wei]:=a[k,i];
b[a[k,i]]:=false;
end;
end;
b[t[tou]]:=true;
inc(tou);
end;
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;
procedure spfa2;
var t:array[1..10000]of longint;
b:array[1..1000]of boolean;
i,j,k,tou,wei:longint;
begin
fillchar(b,sizeof(b),true);
b[n]:=false; t[1]:=n;
fan:=v;
tou:=1;wei:=1;
while tou<=wei do
begin
k:=t[tou];
if tou>100000 then break;
for i:=1 to a[k,0] do
begin
if fan[a[k,i]]<max(v[a[k,i]],fan[k]) then fan[a[k,i]]:=max(fan[k],v[a[k,i]]);;
if b[a[k,i]] then
begin
inc(wei);
t[wei]:=a[k,i];
b[a[k,i]]:=false;
end;
end;
b[t[tou]]:=true;
inc(tou);
end;
end;
procedure int;
var i,j,k,l:longint;
begin
assign(input,'1.in');
reset(input);
readln(n,m);
for i:=1 to n do read(v[i]);
for i:=1 to m do
begin
readln(j,k,l);
if l=1 then
begin
inc(a[j,0]);
a[j,a[j,0]]:=k;
end
else
begin
inc(a[j,0]);
a[j,a[j,0]]:=k;
inc(a[k,0]);
a[k,a[k,0]]:=j;
end;
end;
end;
begin
int;
spfa;
spfa2;
k:=0;
for i:=1 to n do k:=max(k,fan[i]-zheng[i]);
if k>0 then write(k)
else write(0);
end.
牛门看看那里错了。。。
状态: Accepted
测评机: Xeond[6]
得分: 100分
提交日期: 2010-11-8 15:16:00
有效耗时: 4047毫秒
测试结果1: 通过本测试点|有效耗时188ms
测试结果2: 通过本测试点|有效耗时62ms
测试结果3: 通过本测试点|有效耗时188ms
测试结果4: 通过本测试点|有效耗时609ms
测试结果5: 通过本测试点|有效耗时719ms
测试结果6: 通过本测试点|有效耗时172ms
测试结果7: 通过本测试点|有效耗时203ms
测试结果8: 通过本测试点|有效耗时422ms
测试结果9: 通过本测试点|有效耗时750ms
测试结果10: 通过本测试点|有效耗时734ms
type
node=record
sta,en:longint;
end;
var
map:array[1..1000000] of node;
k,cost,max,min:array[1..100000] of longint;
mark:array[1..100000] of boolean;
f:array[1..1000000] of longint;
tol,x,y,z,now,head,tail,n,i,m:longint;
procedure qsort(g,h:longint);
var
head,tail:longint;
mid:node;
begin
head:=g;tail:=h;mid:=map[g];
while g<h do
begin
while (g<h)and(map[h].sta>=mid.sta) do h:=h-1;
map[g]:=map[h];
while (g<h)and(map[g].sta<=mid.sta) do g:=g+1;
map[h]:=map[g];
end;
map[g]:=mid;
if head<g-1 then qsort(head,g-1);
if tail>g+1 then qsort(g+1,tail);
end;
procedure init;
begin
readln(n,m);
for i:=1 to n do
begin
read(cost[i]);
min[i]:=cost[i];
end;
readln;
for i:=1 to m do
begin
readln(x,y,z);
inc(tol);
map[tol].sta:=x;
map[tol].en:=y;
if z=2 then
begin
inc(tol);
map[tol].sta:=y;
map[tol].en:=x;
end;
end;
end;
procedure fill;
begin
fillchar(max,sizeof(max),$ff);
max[1]:=0;
fillchar(f,sizeof(f),0);
head:=1;tail:=1;
f[1]:=1;
fillchar(mark,sizeof(mark),true);
mark[1]:=false;
qsort(1,tol);
for i:=1 to tol do
if k[map[i].sta]=0 then k[map[i].sta]:=i;
k[n+1]:=tol+1;
for i:=n downto 1 do
if k[i]=0 then k[i]:=f[i+1];
end;
begin
init;
fill;
while head<=tail do
begin
now:=f[head];
for i:=k[now] to k[now+1]-1 do
if (max[now]>max[map[i].en])or(min[now]<min[map[i].en])then
begin
if min[now]<min[map[i].en] then min[map[i].en]:=min[now];
if max[now]>max[map[i].en] then max[map[i].en]:=max[now];
if cost[map[i].en]-min[map[i].en]>max[map[i].en] then
max[map[i].en]:=cost[map[i].en]-min[map[i].en];
if mark[map[i].en] then
begin
tail:=tail+1;
f[tail]:=map[i].en;
mark[map[i].en]:=false;
end;
end;
head:=head+1;
mark[now]:=true;
end;
writeln(max[n]);
end.