?? 例三 layout.pas
字號:
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;
{用Bellman-Ford求最短路,并判斷是否存在負權圈}
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.
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -