（最短路径问题）无向连通图 G 有 n 个结点，依次编号为 1,2,3,...,n。用邻接矩阵的形式给出每条边的边长，要求输出以结点 1 为起点出发，到各结点的最短路径长度。 使用 Dijkstra 算法解决该问题：利用 dist 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展，更新与 v 相邻的结点的 dist 值；不断进行上述操作直至所有结点均被扩展，此时 dist 数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）
const MAXV = 100; var n, i, j, v : longint; w : array [1..MAXV, 1..MAXV] of longint; // 邻接矩阵，记录边长 // 其中 w[i, j]为连接结点 i和结点 j的无向边长度，若无边则为-1 dist : array [1..MAXV] of longint; used : array [1..MAXV] of longint; // 记录结点是否已扩展（0：未扩展；1：已扩展） begin read(n); for i := 1 to n do for j := 1 to n do read(w[i, j]); dist[1] := 0; for i := 2 to n do dist[i] := -1; for i := 1 to n do used[i] := 0; while true do begin 1; for i := 1 to n do if (used[i] <> 1) and (dist[i] <> -1) and ((v = -1) or (2)) then 3; if v = -1 then break; 4; for i := 1 to n do if (w[v, i] <> -1) and ((dist[i] = -1) or (5)) then dist[i] := dist[v] + w[v, i]; end; for i := 1 to n do writeln(dist[i]); end.
