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

Submission #18810

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, 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:34:48+0900 C - 暗闇帰り道 rankugai C++ (G++ 4.6.4) 0 1463 Byte WA 5045 ms 101468 KB

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 15 WA × 14 TLE × 27 MLE × 8
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 23 ms 780 KB
00_mini_02.txt AC 21 ms 788 KB
00_mini_03.txt AC 21 ms 788 KB
00_mini_04.txt AC 20 ms 784 KB
00_mini_05.txt AC 22 ms 816 KB
00_sample_01.txt AC 21 ms 736 KB
00_sample_02.txt AC 21 ms 764 KB
01_rnd_01.txt MLE 4794 ms 100956 KB
01_rnd_02.txt MLE 4935 ms 100024 KB
01_rnd_03.txt WA 117 ms 7260 KB
01_rnd_04.txt WA 2430 ms 50268 KB
01_rnd_05.txt WA 89 ms 4088 KB
01_rnd_06.txt AC 31 ms 1296 KB
01_rnd_07.txt WA 95 ms 4200 KB
01_rnd_08.txt TLE 5039 ms 100192 KB
01_rnd_09.txt MLE 0 ms 100704 KB
01_rnd_10.txt TLE 5036 ms 100440 KB
01_rnd_11.txt TLE 5035 ms 50920 KB
01_rnd_12.txt WA 3112 ms 50652 KB
01_rnd_13.txt WA 1130 ms 13284 KB
01_rnd_14.txt TLE 5033 ms 26724 KB
01_rnd_15.txt TLE 5033 ms 50916 KB
01_rnd_16.txt AC 39 ms 1728 KB
01_rnd_17.txt TLE 5031 ms 13924 KB
01_rnd_18.txt AC 2868 ms 892 KB
01_rnd_19.txt AC 993 ms 1144 KB
01_rnd_20.txt AC 4814 ms 984 KB
02_maxrnd_01.txt TLE 5040 ms 101348 KB
02_maxrnd_02.txt MLE 4948 ms 101360 KB
02_maxrnd_03.txt TLE 5045 ms 101340 KB
02_maxrnd_04.txt TLE 5037 ms 101340 KB
02_maxrnd_05.txt TLE 5038 ms 101464 KB
02_maxrnd_06.txt TLE 5039 ms 101344 KB
02_maxrnd_07.txt WA 2440 ms 52200 KB
02_maxrnd_08.txt WA 368 ms 15336 KB
02_maxrnd_09.txt TLE 5040 ms 101344 KB
02_maxrnd_10.txt MLE 4263 ms 101340 KB
02_maxrnd_11.txt TLE 5037 ms 101468 KB
02_maxrnd_12.txt TLE 5035 ms 52196 KB
02_maxrnd_13.txt TLE 5035 ms 52196 KB
02_maxrnd_14.txt TLE 5032 ms 52292 KB
02_maxrnd_15.txt WA 1897 ms 15332 KB
02_maxrnd_16.txt TLE 5031 ms 27720 KB
02_maxrnd_17.txt TLE 5031 ms 15336 KB
02_maxrnd_18.txt TLE 5029 ms 4600 KB
02_maxrnd_19.txt TLE 5029 ms 3844 KB
03_hard_01.txt TLE 5041 ms 101468 KB
03_hard_02.txt MLE 3685 ms 101468 KB
03_hard_03.txt TLE 5031 ms 3580 KB
03_hard_04.txt TLE 5030 ms 3552 KB
03_hard_05.txt MLE 4984 ms 101468 KB
03_hard_06.txt MLE 3922 ms 101468 KB
03_hard_07.txt TLE 5029 ms 3516 KB
03_hard_08.txt TLE 5030 ms 3836 KB
04_open_01.txt TLE 5031 ms 9204 KB
04_open_02.txt TLE 5038 ms 101356 KB
05_minihard_01.txt WA 52 ms 3952 KB
05_minihard_02.txt WA 65 ms 3952 KB
05_minihard_03.txt AC 44 ms 772 KB
05_minihard_04.txt AC 52 ms 784 KB
05_minihard_05.txt WA 55 ms 3952 KB
05_minihard_06.txt WA 94 ms 3932 KB
05_minihard_07.txt AC 63 ms 888 KB
05_minihard_08.txt WA 100 ms 868 KB