比赛 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.