比赛 |
20101116 |
评测结果 |
ATTTTTTTTA |
题目名称 |
城市 |
最终得分 |
20 |
用户昵称 |
itachi |
运行时间 |
0.000 s |
代码语言 |
Pascal |
内存使用 |
0.00 MiB |
提交时间 |
2010-11-16 11:06:11 |
显示代码纯文本
program t4(input,output);
var
m,n,u,v,s,i,j,ans:longint;
fi:array[1..10000]of longint;
data:array[1..10000,0..1000]of integer;
oil:array[1..10000,1..1000]of longint;
procedure init;
var
ai,bi,ci:longint;
begin
readln(n,m,u,v,s);
for i:= 1 to n do
readln(fi[i]);
for i:= 1 to n do
data[i,0]:=0;
for i:= 1 to m do
begin
readln(ai,bi,ci);
if ai<>bi then
begin
if ci<=s then
begin
inc(data[ai,0]);
data[ai,data[ai,0]]:=bi;
oil[ai,data[ai,0]]:=ci;
inc(data[bi,0]);
data[bi,data[bi,0]]:=ai;
oil[bi,data[bi,0]]:=ci;
end;
end;
end;
close(input);
end;
procedure dfs(ss,oi,t:longint);
var
i,k:longint;
begin
if ss=v then
begin
if t<ans then ans:=t;
exit;
end;
for i := 1 to data[ss,0] do
begin
k:=data[ss,i];
if oi+oil[ss,i]<= s
then
begin
if fi[k]>t
then dfs(k,oi+oil[ss,i],fi[k])
else dfs(k,oi+oil[ss,i],t);
end;
end;
end;
begin
assign(input,'cost.in');
reset(input);
assign(output,'cost.out');
rewrite(output);
init;
ans:=maxlongint;
dfs(u,0,fi[u]) ;
if ans<>maxlongint then
writeln(ans) else writeln(-1);
close(output);
end.