当前没有测试数据。

28．（完善程序）

（最短路径问题）无向连通图 $G$ 有 $n$ 个结点，依次编号为 $0,1,2,...,(n-1)$。用邻接矩阵的形式给出每条边的边长，要求输出以结点 $0$ 为起点出发，到各结点的最短路径长度。使用 Dijkstra 算法解决该问题：

利用 $dist$ 数组记录当前各结点与起点的已找到的最短路径长度；每次从未扩展的结点中选取 $dist$ 值最小的结点 $v$ 进行扩展，更新与 $v$ 相邻的结点的 $dist$ 值；不断进行上述操作直至所有结点均被扩展，此时 $dist$ 数据中记录的值即为各结点与起点的最短路径长度。（第五空 2 分，其余 3 分）

#include<iostream>
using namespace std;

const int MAXV=100;
int n,i, j, v; 
int w[MAXV][MAXV]; // 邻接矩阵，记录边长 
// 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度，若无边则为-1 
int dist[MAXV]; 
int used[MAXV]; // 记录结点是否已扩展（0：未扩展；1：已扩展） 
 
int main(){ 
  cin>>n;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      cin>>w[i][j];
  dist[0]=0;
  for(i=1;i<n;i++)
    dist[i]=-1;
  for(i=0;i<n;i++)
    used[i]=0;
  while(true){
    ____________________; 
    for(i=0;i<n;i++)
      if(used[i]!=1&&dist[i]!=-1&&(v==-1||____________________))
        ____________________; 
    if(v==-1)
      break; 
    ____________________; 
    for(i=0;i<n;i++)
      if(w[v][i]!=-1&&(dist[i]==-1||____________________)) 
        dist[i]=dist[v]+w[v][i];
  } 
  for(i=0;i<n;i++)
    cout<<dist[i]<<endl;
  return 0;
} 

①：{{ input(1) }}

②：{{ input(2) }}

③：{{ input(3) }}

④：{{ input(4) }}

⑤：{{ input(5) }}