对于每一个城市 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 5; inc(t); queue[t] := point[j]; end; j := next[j]; inc(s); end; answer := 0; for j := 1 to n do inc(answer, 1 - visit[j]); writeln(i, ':', answer - 1); end; end.
