If (4) then answer[i] := previous[i]
else
answer[i] := next[i]; next[previous[i]] := next[i]; (5) ; end;
for i := 2 to n do
writeln(i, ':', answer[i]); end.
2. （交通中断）有一个小国家，国家内有 n 座城市和 m 条双向的道路，每条道路连接着两座不同的城市。其中 1 号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i>1)个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第 i 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。
对于每一个城市 i，假定只有第 i 个城市
与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息，其中 head[x]表示顶点 x 的第一条边的编号，next[i]表示第 i 条边的下一条边的编号，point[i]表示第 i 条边的终点，weight[i]表示第 i 条边的长度。（第一空 2 分，其余 3 分） const
maxn = 6000; maxm = 100000; inf = 2147483647; var
next, point, weight: array[1..maxm] of longint;
head, dist, visit: array[1..maxn] of longint;
queue: array[0..maxn - 1] of longint; n, m, i, j, s, t, total, x, y, z, answer: longint;
procedure link(x, y, z: longint);
begin
inc(total);
next[total] := head[x]; head[x] := total; point[total] := y; weight[total] := z; inc(total);
next[total] := head[y]; head[y] := total; point[total] := x; weight[total] := z; end; begin
total := 0; readln(n, m); for i := 1 to m do begin
readln(x, y, z); link(x, y, z); end;
for i := 1 to n do dist[i] := inf;
(1) ; queue[1] := 1; visit[1] := 1; s := 1; t := 1;
// 使用 SPFA 求出第一个点到其余各点的最短路长度
while s <= t do begin
x := queue[s mod maxn]; j := head[x]; while j <> 0 do begin
if (2) then
begin
dist[point[j]] := dist[x] + weight[j];
if (visit[point[j]] = 0) then begin inc(t);
queue[t mod maxn] := point[j]; visit[point[j]] := 1; end;
end;
j := next[j]; end;
(3) ;
inc(s); end;
for i := 2 to n do begin
queue[1] := 1;
fillchar(visit, sizeof(visit), 0); visit[1] := 1; s := 1; t := 1;
while s <= t do // 判断最短路长度是否不变 begin
x := queue[s]; j := head[x]; while j <> 0 do
if
(point[j]
<>
i)
and
( (4) )
and (visit[point[j]] = 0) then begin
NOIP2016年第二十二届全国青少年信息学奥林匹克联赛提高组初赛(pascal)
