changed 5 years ago
Linked with GitHub

Dijkstra Note

介紹dijkstraㄉ文章:

http://www.csie.ntnu.edu.tw/~u91029/Path.html
可以先讀一下喔 :pouting_cat:


以走迷宮圖的最短路徑為例 :hamster:

https://zerojudge.tw/ShowProblem?problemid=d793

#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'; } }

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 INF INF INF
7 INF INF INF INF
INF INF INF INF INF
INF INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (0 , 1) ,距離: 3 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 INF INF
7 6 INF INF INF
INF INF INF INF INF
INF INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (0 , 2) ,距離: 4 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 INF
7 6 8 INF INF
INF INF INF INF INF
INF INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (1 , 1) ,距離: 6 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 INF
7 6 8 INF INF
INF 13 INF INF INF
INF INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (0 , 3) ,距離: 6 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
INF 13 INF INF INF
INF INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (1 , 0) ,距離: 7 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 INF INF INF
INF INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (2 , 0) ,距離: 8 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 INF INF INF
10 INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (1 , 2) ,距離: 8 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 13 INF INF
10 INF INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (3 , 0) ,距離: 10 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 13 INF INF
10 13 INF INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (2 , 2) ,距離: 13 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 13 18 INF
10 13 17 INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (3 , 1) ,距離: 13 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 13 18 INF
10 13 17 INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (2 , 1) ,距離: 13 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 INF
8 13 13 18 INF
10 13 17 INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (1 , 3) ,距離: 15 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 INF
10 13 17 INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (0 , 4) ,距離: 15 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 INF
10 13 17 INF INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (3 , 2) ,距離: 17 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 INF
10 13 17 19 INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (2 , 3) ,距離: 18 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 21
10 13 17 19 INF
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (3 , 3) ,距離: 19 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 21
10 13 17 19 24
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (2 , 4) ,距離: 21 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 21
10 13 17 19 24
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (3 , 4) ,距離: 24 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 21
10 13 17 19 24
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (1 , 4) ,距離: 24 :dog:

0 3 1 2 9
7 3 4 9 9
1 7 5 5 3
2 3 4 2 5
0 3 4 6 15
7 6 8 15 24
8 13 13 18 21
10 13 17 19 24
透過綠色這格更新旁邊的紅色格ㄉ最短路徑,再從所有格子中挑選未走過且路徑最短者繼續尋找 ,即格子: (1 , 4) ,距離: 24 :dog:

Select a repo