Contest Duration: - (local time) (90 minutes) Back to Home

Submission #18794

Source Code Expand

Copy
```#include <cmath>
#include <iostream>
#include <queue>

using namespace std;

const int dy[4] = {1, 0, -1, 0};
const int dx[4] = {0, 1, 0, -1};

struct node {

int y, x, t;
double drk;

node(int y, int x, int t, double drk)
: y(y), x(x), t(t), drk(drk) {}

};

bool operator <(node a, node b) {

return a.drk < b.drk;

}

int main() {

int N, M;
cin >> N >> M;
vector<vector<char> > c(N, vector<char>(M));
int sy, sx;
for (int y = 0; y < N; ++y) {
for (int x = 0; x < M; ++x) {
cin >> c[y][x];
if (c[y][x] == 's') {
sy = y;
sx = x;
}
}
}

priority_queue<node> q;
vector<vector<double> > mem(N, vector<double>(M, 10.0));
q.push(node(sy, sx, 0, 9.0));
while (!q.empty()) {
node tmp = q.top();
q.pop();
int y = tmp.y;
int x = tmp.x;
int t = tmp.t;
double drk = tmp.drk;
if (y < 0 || y >= N) continue;
if (x < 0 || x >= M) continue;
if (c[y][x] == '#') continue;
if (c[y][x] == 'g') {
printf("%.16f\n", drk);
goto succ;
}
if (drk >= mem[y][x]) continue;
mem[y][x] = drk;
double ndrk = drk;
if ('1' <= c[y][x] && c[y][x] <= '9') {
ndrk = min(ndrk, (c[y][x] - '0') * pow(0.99, t));
}
for (int i = 0; i < 4; ++i) {
q.push(node(y + dy[i], x + dx[i], t + 1, ndrk));
}
}
puts("-1");
succ:;

return 0;

}
```

#### Submission Info

Submission Time 2012-05-27 20:33:52+0900 C - 暗闇帰り道 rankugai C++ (G++ 4.6.4) 0 1444 Byte CE

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:56:28: error: ‘printf’ was not declared in this scope
./Main.cpp:69:12: error: ‘puts’ was not declared in this scope
```