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
| #include <iostream>
#include <queue>
#define INF 2000000000
using namespace std;
int n, map[125][125], os[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }, save[125][125];
bool check[125][125];
priority_queue<pair<int, pair<int,int>>> q;
int dijk();
int min(int a, int b) {
return a > b ? b : a;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int idx = 1;
while (true) {
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> map[i][j];
check[i][j] = false;
}
cout << "Problem " << idx++ << ": " << dijk() << endl;
}
}
int dijk() {
q.push({ -map[0][0] , {0,0 } });
save[0][0] = map[0][0];
while (!q.empty()) {
int cur = -q.top().first, r = q.top().second.first, c = q.top().second.second;
q.pop();
if (check[r][c])
continue;
check[r][c] = true;
save[r][c] = cur;
for (int i = 0; i < 4; i++) {
int nr = r + os[i][0], nc = c + os[i][1];
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !check[nr][nc]) {
int ncur = cur + map[nr][nc];
q.push({ -ncur, {nr, nc} });
}
}
}
return save[n - 1][n - 1];
}
|
