SGU 103 — Traffic lights
Dijkstra的改进方法.
考虑依然能够满足贪心,而且没有负权环,所以只要用dijkstra,在更新的时候加上等待时间就可以.
等待时间用waittime子程序判断,注意waittime子程序判断-1的时候要注意,详见WindyWinter牛的题解:
http://www.briefdream.com/sgu-103/
剩下没什么了.
第一次提交WA,忘了判断无解=.=.
第二次提交RE,n的范围是300我开成200了…
然后AC…
准确性还算可以…Dijkstra好久没写了…
{
SGU 103; Traffic lights
- sqybi’s code
- Dijkstra (extended)
}
//for my winsty
program sgu103_sqybi;
const
nn = 300;
var
s, t, n, m, i, j, k, min, x, y, z, r: longint;
ch: char;
a: array[1..nn]of record
c: boolean;
w, b, p: longint;
end;
table: array[1..nn, 1..nn]of longint;
path, dist: array[1..nn]of longint;
flag: array[1..nn]of boolean;
function min_(x, y: longint): longint;
begin
if x < y then min_ := x else min_ := y;
end;
procedure getcolor(time, x: longint; var f: boolean; var t: longint);
begin
if time < a[x].w then begin
f := a[x].c;
t := a[x].w - time;
exit;
end;
time := time - a[x].w;
time := time mod (a[x].b + a[x].p);
if a[x].c then begin
if time < a[x].p then begin
f := false;
t := a[x].p - time;
end
else begin
f := true;
t := a[x].b + a[x].p - time;
end;
end
else begin
if time < a[x].b then begin
f := true;
t := a[x].b - time;
end
else begin
f := false;
t := a[x].b + a[x].p - time;
end;
end;
end;
function waittime(time, x, y: longint): longint;
var
r, tx, ty: longint;
fx, fy: boolean;
begin
r := 0;
getcolor(time, x, fx, tx);
getcolor(time, y, fy, ty);
if fx = fy then begin
waittime := r;
exit;
end;
r := r + min_(tx, ty);
time := time + min_(tx, ty);
getcolor(time, x, fx, tx);
getcolor(time, y, fy, ty);
if fx = fy then begin
waittime := r;
exit;
end;
r := r + min_(tx, ty);
time := time + min_(tx, ty);
getcolor(time, x, fx, tx);
getcolor(time, y, fy, ty);
if fx = fy then begin
waittime := r;
exit;
end;
waittime := -1;
end;
procedure print(x: longint);
begin
if path[x] <> 0 then print(path[x]);
write(x, ‘ ‘);
end;
begin
reset(input);
rewrite(output);
readln(s, t);
readln(n, m);
for i:=1 to n do begin
read(ch);
if ch = ‘B’ then a[i].c := true;
readln(a[i].w, a[i].b, a[i].p);
end;
for i:=1 to m do begin
readln(x, y, z);
table[x, y] := z;
table[y, x] := z;
end;
fillchar(flag, sizeof(flag), false);
fillchar(dist, sizeof(dist), $FF);
dist[s] := 0;
for i:=1 to n-1 do begin
min := maxlongint;
for j:=1 to n do
if not flag[j] and (dist[j] <> -1) and (min > dist[j]) then begin
min := dist[j];
k := j;
end;
flag[k] := true;
if k = t then break;
for j:=1 to n do begin
if table[j, k] = 0 then continue;
r := waittime(dist[k], j, k);
if r = -1 then continue;
r := dist[k] + r + table[j, k];
if not flag[j] and ((dist[j] = -1) or (dist[j] > r)) then begin
dist[j] := r;
path[j] := k;
end;
end;
end;
if dist[t] <> -1 then begin
writeln(dist[t]);
print(t);
end
else
writeln(0);
end.
阅读(107 次)