Dijkstra Note

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <bits/stdc++.h>
using namespace std;

typedef struct Node {
    int i;
    int j;
    int dis;
    bool operator<(const Node& a) const {
        return a.dis < dis;
    }
} node;

int ta, N, M;  // taskAmount
int maze[1000][1000];
int dis[1000][1000];
bool flag[1000][1000];
int mv[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
priority_queue<node> dispq;

void dijsktra() {
    while (!dispq.empty()) {
        flag[dispq.top().i][dispq.top().j] = true;
        for (int k = 0; k < 4; k++) {
            node nn;  //nextNode
            nn.i = dispq.top().i + mv[k][0];
            nn.j = dispq.top().j + mv[k][1];
            nn.dis = dis[nn.i][nn.j];
            if ((nn.i < N && nn.i >= 0) && (nn.j < M && nn.j >= 0) && (!flag[nn.i][nn.j])) {
                if (dispq.top().dis + maze[nn.i][nn.j] < nn.dis) {
                    nn.dis = dispq.top().dis + maze[nn.i][nn.j];
                    dispq.push(nn);
                    dis[nn.i][nn.j] = nn.dis;
                }
            }
        }
        dispq.pop();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> ta;
    while (ta--) {
        //int p[1000][1000];
        cin >> N >> M;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> maze[i][j];
                flag[i][j] = 0;
                dis[i][j] = 9999999;
            }
        }
        node n = {0, 0, maze[0][0]};
        dis[0][0] = maze[0][0];
        dispq.push(n);

        dijsktra();
        cout << dis[N - 1][M - 1] << '\n';
    }
}