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