3. 【NOIP2015】最短路径问题

无向连通图 G 有 n 个结点，依次编号为 1,2,3,⋯,n。用邻接矩阵的形式给出每条边的边长，要求输出以结点 1 为起点出发，到各结点的最短路径长度。使用 Dijkstra 算法解决该问题：利用dist数组记录当前各结点与起点的巳找到的最短 路径长度；每次从未扩展的结点中选取dist值最小的结点v进行扩展，更新与v相邻结点的dist值；不断进行上述操作直至所有结点均被扩展，此时dist数据中记录的值即为各结点与 起点的最短路径长度。

补全程序：

#include<iostream>
using namespace std;
const int MAXV=100;
int n,i,j,v;
int w[MAXV][MAXV];
int dist[MAXV];
int used[MAXV];
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;
}

选择题：

1. ①处应填（ ）
   {{ select(1) }}

• v=0
• v=-1
• dist[v]=1
• dist[v]=0

2. ②处应填（ ）
   {{ select(2) }}

• dist[v]=-1
• v=n-1
• used[i]=1
• dist[i]<=dist[v]

3. ③处应填（ ）
   {{ select(3) }}

• used[i]=1
• used[v]=1
• v++
• v=i

4. ④处应填（ ）
   {{ select(4) }}

• w[v][v]=0
• w[v][v]=1
• used[v]=1
• dist[v]++

5. ⑤处应填（ ）
   {{ select(5) }}

• !used[v]
• !used[i]
• dist[v]-dist[i]+(used[i]==1)<=w[v][i]
• dist[v]+w[v][i]<=dist[i]