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
Task C - 暗闇帰り道
User rankugai
Language C++ (G++ 4.6.4)
Score 0
Code Size 1461 Byte
Status MLE
Exec Time 5036 ms
Memory 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