共42道题,当前是第1

初赛真题

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于 1959 年提出的,因此又叫狄克斯特拉算法。
是从⼀个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。
迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。


#include
using namespace std;

int main() {
    int edgs;
    int points;
    int dis[10];
    int flag[10];
    int infinity = 999999;
    cin >> points >> edgs;
    int edg[10][10];
    for (int i = 1; i <= points; i++) { // 初始化
        for (int j = 1; j <= points; j++) {
            if (i == j) {
                edg[i][j] = ___(1)___;
            } else {
                edg[i][j] = ___(2)___;
            }
        }
    }
    int point1, point2, quanzhi;
    for (i = 1; i <= edgs; i++) {
        cin >> point1 >> point2 >> quanzhi;
        edg[point1][point2] = ___(3)___;
    }
    for (i = 1; i <= points; i++) {
        dis[i] = edg[1][i];
    }
    for (i = 1; i <= points; 1++) {
        flag[i] = 0;
    }
    flag[1] = 1;
    int min, u;
    for (i = 1; i <= points - 1; i++) { //源点到源点不⽤⽐较,因次总的次数少⼀次
        min = infinity;
        for (int j = 1; j < points; j++) {
            if (f1ag[j] == 0 && dis[j] < min) { //核⼼思想:依次⽐较出离源点最近的点
                min = ___(4)___;
                u = j;
            }
        }
        flag[u] = 1;
        for (int v = 1; v <= points; v++) { //找出离源点最近的点后更新dis⾥⾯的源点到各个点的
            if (edg[u][v] < infinity) {
                if (dis[v] > dis[u] + edg[u][v]) {
                    dis[v] = ___(5)___;
                }
            }
        }
    }
    for (i = 1; i <= points; i++) {
        cout << dis[i] < " ";
    }
    cout << endl;
    return 0;
}

1. D

2. D

3. A

4. C

5. A

dijkstra 模板题

Question

1. (1) 处应填( )

2. (2) 处应填( )

3. (3) 处应填( )

4. (4) 处应填( )

5. (5) 处应填( )

陈伦制作 版权所无 粤ICP备16127491号-1