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

Submission #19822

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;
}
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) {
int ny = y + dy[i];
int nx = x + dx[i];
if (mem[ny][nx] < ndrk)
q.push(node(ny, nx, t + 1, ndrk));
}
}
puts("-1");
succ:;

return 0;

}
```

Submission Info

Submission Time 2012-05-28 09:16:58+0900 C - 暗闇帰り道 rankugai C++ (G++ 4.6.4) 0 1498 Byte RE 372 ms 4604 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 5 WA × 9 RE × 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 RE 252 ms 796 KB
00_mini_02.txt RE 254 ms 796 KB
00_mini_03.txt RE 247 ms 792 KB
00_mini_04.txt RE 251 ms 792 KB
00_mini_05.txt RE 247 ms 744 KB
00_sample_01.txt RE 249 ms 796 KB
00_sample_02.txt RE 249 ms 796 KB
01_rnd_01.txt RE 352 ms 4188 KB
01_rnd_02.txt WA 51 ms 2428 KB
01_rnd_03.txt RE 259 ms 1044 KB
01_rnd_04.txt RE 261 ms 1144 KB
01_rnd_05.txt RE 245 ms 792 KB
01_rnd_06.txt RE 248 ms 792 KB
01_rnd_07.txt WA 24 ms 1020 KB
01_rnd_08.txt WA 62 ms 2684 KB
01_rnd_09.txt RE 281 ms 2744 KB
01_rnd_10.txt RE 263 ms 2172 KB
01_rnd_11.txt RE 257 ms 1656 KB
01_rnd_12.txt RE 266 ms 1648 KB
01_rnd_13.txt RE 248 ms 892 KB
01_rnd_14.txt RE 267 ms 2172 KB
01_rnd_15.txt RE 262 ms 1792 KB
01_rnd_16.txt AC 27 ms 1276 KB
01_rnd_17.txt RE 263 ms 1528 KB
01_rnd_18.txt AC 22 ms 912 KB
01_rnd_19.txt RE 253 ms 1144 KB
01_rnd_20.txt AC 23 ms 912 KB
02_maxrnd_01.txt RE 284 ms 3532 KB
02_maxrnd_02.txt WA 83 ms 4604 KB
02_maxrnd_03.txt RE 270 ms 3068 KB
02_maxrnd_04.txt WA 130 ms 4592 KB
02_maxrnd_05.txt RE 274 ms 3148 KB
02_maxrnd_06.txt RE 281 ms 3256 KB
02_maxrnd_07.txt WA 62 ms 3504 KB
02_maxrnd_08.txt WA 50 ms 3260 KB
02_maxrnd_09.txt RE 315 ms 3840 KB
02_maxrnd_10.txt WA 75 ms 3840 KB
02_maxrnd_11.txt RE 372 ms 3824 KB
02_maxrnd_12.txt WA 126 ms 3808 KB
02_maxrnd_13.txt RE 347 ms 3844 KB
02_maxrnd_14.txt RE 358 ms 3524 KB
02_maxrnd_15.txt RE 279 ms 3060 KB
02_maxrnd_16.txt RE 302 ms 3068 KB
02_maxrnd_17.txt RE 288 ms 3064 KB
02_maxrnd_18.txt AC 49 ms 2936 KB
02_maxrnd_19.txt AC 48 ms 3044 KB
03_hard_01.txt RE 275 ms 2940 KB
03_hard_02.txt RE 273 ms 2948 KB
03_hard_03.txt RE 270 ms 2928 KB
03_hard_04.txt RE 276 ms 2932 KB
03_hard_05.txt RE 272 ms 2932 KB
03_hard_06.txt RE 271 ms 2940 KB
03_hard_07.txt RE 273 ms 2940 KB
03_hard_08.txt RE 274 ms 2940 KB
04_open_01.txt RE 279 ms 2936 KB
04_open_02.txt RE 272 ms 2944 KB
05_minihard_01.txt RE 248 ms 792 KB
05_minihard_02.txt RE 250 ms 768 KB
05_minihard_03.txt RE 246 ms 788 KB
05_minihard_04.txt RE 246 ms 792 KB
05_minihard_05.txt RE 249 ms 780 KB
05_minihard_06.txt RE 252 ms 784 KB
05_minihard_07.txt RE 257 ms 788 KB
05_minihard_08.txt RE 248 ms 780 KB