4485번: 녹색 옷 입은 애가 젤다지?
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주
www.acmicpc.net
다익스트라 기초에 2차원좌표가 추가되었습니다.
출발지점는 (0, 0)이고 도착지점은 (N - 1, N - 1)입니다.
그럼 (0, 0)에서 출발하여 각 칸까지의 최소비용을 구해주시면 됩니다.
|
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <iostream>
#include <queue>
#include <cstring>
#define INF 1000000000
using namespace std;
typedef struct Point {
int x;
int y;
int dis;
}Point;
int list[125][125], d[125][125];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N;
struct compare {
bool operator()(Point a, Point b) {
return a.dis > b.dis;
}
};
void dijkstra() {
priority_queue<Point, vector<Point>, compare> q;
q.push({ 0,0,list[0][0] });
d[0][0] = list[0][0];
while (!q.empty()) {
int x = q.top().x;
int y = q.top().y;
int dis = q.top().dis;
q.pop();
if (d[x][y] < dis) continue;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
int nextdis = dis + list[nx][ny];
if (d[nx][ny] > nextdis) {
d[nx][ny] = nextdis;
q.push({ nx, ny, nextdis });
}
}
}
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> list[i][j];
}
}
}
void init() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
d[i][j] = INF;
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
for (int t = 1; ; t++) {
input();
if (!N) return 0;
init();
dijkstra();
cout << "Problem " << t << ": " << d[N - 1][N - 1] << '\n';
}
}
|
cs |
'algorithm > dijkstra' 카테고리의 다른 글
| boj 18352 특정 거리의 도시 찾기 (0) | 2021.03.22 |
|---|---|
| boj 14496 그대, 그머가 되어 (0) | 2021.03.22 |