123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 |
- Program Usaco_Dec05_layout;
- Const
- Fin = 'layout.in';
- Fou = 'layout.out';
- MaxW = 1100000000;
- Maxn = 1000;
- Maxm = 22000;
- Var
- Dist: Array[1 .. Maxn]of Longint;
- a, b, d: Array[1 .. Maxm]of Longint;
- n, m, ML, MD: Longint;
- Procedure Init;
- Var
- l, i, j, k: Longint;
- Begin
- Assign(Input, Fin);
- Reset(Input);
- Read(n, ML, MD);
- m:= 0;
-
- For l:= 2 to n do
- Begin
- Inc(m);
- a[m]:= l;
- b[m]:= l - 1;
- d[m]:= 0;
- End;
-
- For l:= 1 to ML do
- Begin
- Read(i, j);
- If i > j then
- Begin
- k:= i;
- i:= j;
- j:= k;
- End;
- Read(k);
- Inc(m);
- a[m]:= i;
- b[m]:= j;
- d[m]:= k;
- End;
-
- For l:= 1 to MD do
- Begin
- Read(i, j);
- If i > j then
- Begin
- k:= i;
- i:= j;
- j:= k;
- End;
- Read(k);
- Inc(m);
- a[m]:= j;
- b[m]:= i;
- d[m]:= -k;
- End;
- Close(Input);
- End;
- Procedure Main;
- Var
- i, tmp, tot: Longint;
- Quit: Boolean;
- Begin
- For i:= 2 to n do Dist[i]:= MaxW;
- Dist[1]:= 0;
- tot:= 0;
-
- Repeat
- Inc(tot);
- Quit:= True;
- For i:= 1 to m do
- Begin
- tmp:= Dist[a[i]] + d[i];
- If tmp < Dist[b[i]] then
- Begin
- Dist[b[i]]:= tmp;
- Quit:= False;
- End;
- End;
- Until Quit Or (tot > n);
- Assign(Output, Fou);
- Rewrite(Output);
- If (tot > n) then Writeln(-1)
- Else
- If (Dist[n] = MaxW) then Writeln(-2)
- Else
- Writeln(Dist[n] - Dist[1]);
- Close(Output);
- End;
- Begin
- Init;
- Main;
- End.
|