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