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

Submission #19820

Source Code Expand

Copy
```#include <cmath>
#include <cstdio>
#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, 0.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-28 08:54:22+0900 C - 暗闇帰り道 rankugai C++ (G++ 4.6.4) 0 1461 Byte MLE 5036 ms 101476 KB

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 10 WA × 2 TLE × 2 MLE × 50
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 22 ms 792 KB
00_mini_02.txt AC 22 ms 780 KB
00_mini_03.txt AC 20 ms 812 KB
00_mini_04.txt AC 21 ms 732 KB
00_mini_05.txt AC 22 ms 792 KB
00_sample_01.txt AC 21 ms 792 KB
00_sample_02.txt AC 21 ms 784 KB
01_rnd_01.txt MLE 1181 ms 100964 KB
01_rnd_02.txt MLE 1306 ms 99952 KB
01_rnd_03.txt MLE 1191 ms 99412 KB
01_rnd_04.txt MLE 1259 ms 99548 KB
01_rnd_05.txt MLE 1191 ms 99296 KB
01_rnd_06.txt MLE 1178 ms 99160 KB
01_rnd_07.txt MLE 1255 ms 99412 KB
01_rnd_08.txt MLE 1427 ms 100188 KB
01_rnd_09.txt MLE 1365 ms 100744 KB
01_rnd_10.txt MLE 1236 ms 100440 KB
01_rnd_11.txt MLE 1359 ms 100052 KB
01_rnd_12.txt MLE 1269 ms 99804 KB
01_rnd_13.txt MLE 1525 ms 99292 KB
01_rnd_14.txt MLE 1242 ms 100440 KB
01_rnd_15.txt MLE 1626 ms 100064 KB
01_rnd_16.txt MLE 1853 ms 99680 KB
01_rnd_17.txt MLE 2059 ms 99936 KB
01_rnd_18.txt MLE 2008 ms 99268 KB
01_rnd_19.txt AC 26 ms 1176 KB
01_rnd_20.txt MLE 1911 ms 99300 KB
02_maxrnd_01.txt MLE 1222 ms 101460 KB
02_maxrnd_02.txt MLE 1507 ms 101468 KB
02_maxrnd_03.txt MLE 1286 ms 101464 KB
02_maxrnd_04.txt MLE 1402 ms 101460 KB
02_maxrnd_05.txt MLE 1216 ms 101476 KB
02_maxrnd_06.txt MLE 1294 ms 101464 KB
02_maxrnd_07.txt MLE 1523 ms 101468 KB
02_maxrnd_08.txt MLE 1379 ms 101464 KB
02_maxrnd_09.txt MLE 1314 ms 101448 KB
02_maxrnd_10.txt MLE 1291 ms 101464 KB
02_maxrnd_11.txt MLE 1254 ms 101460 KB
02_maxrnd_12.txt MLE 1393 ms 101464 KB
02_maxrnd_13.txt MLE 1434 ms 101472 KB
02_maxrnd_14.txt MLE 1492 ms 101472 KB
02_maxrnd_15.txt MLE 1568 ms 101464 KB
02_maxrnd_16.txt MLE 1404 ms 101408 KB
02_maxrnd_17.txt MLE 1396 ms 101460 KB
02_maxrnd_18.txt MLE 2207 ms 101464 KB
02_maxrnd_19.txt MLE 1432 ms 101468 KB
03_hard_01.txt MLE 1338 ms 101476 KB
03_hard_02.txt MLE 1406 ms 101392 KB
03_hard_03.txt TLE 5036 ms 52196 KB
03_hard_04.txt TLE 5034 ms 52228 KB
03_hard_05.txt MLE 1436 ms 101468 KB
03_hard_06.txt MLE 1318 ms 101468 KB
03_hard_07.txt MLE 2014 ms 101468 KB
03_hard_08.txt MLE 1367 ms 101468 KB
04_open_01.txt MLE 1761 ms 101468 KB
04_open_02.txt MLE 1183 ms 101476 KB
05_minihard_01.txt WA 22 ms 780 KB
05_minihard_02.txt WA 37 ms 1588 KB
05_minihard_03.txt AC 21 ms 792 KB
05_minihard_04.txt AC 26 ms 796 KB
05_minihard_05.txt MLE 1505 ms 99136 KB
05_minihard_06.txt MLE 1374 ms 99160 KB
05_minihard_07.txt MLE 2821 ms 99160 KB
05_minihard_08.txt MLE 2890 ms 99160 KB