Submission #19820

---

Source Code Expand

#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

Judge Result