五、完善程序-2

信息学奥赛历年真题 2015年NOIP提高组真题五、完善程序-2

(最短路径问题)无向连通图 G 有 n 个结点，依次编号为 0,1,2,…,(n−1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点 0 为起点出发,到各结点的最短路径长度。
使用 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]; // 邻接矩阵，记录边长
// 其中 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;
}

信息学奥赛历年真题

五、完善程序-2

Quiz Summary

Information

Results

Results

Categories

1. Question

2. Question

3. Question

4. Question

5. Question