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

Submission #19016

Source Code Expand

Copy
```#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <complex>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

#define REP(i,x) for(int i=0 ; i<(int)(x) ; i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;

class C{
struct Node{
int next;
int sec;
long double cost;
Node(int n,int s,long double c):next(n),sec(s),cost(c){}
bool operator<(const Node &n)const{
return cost<n.cost;
}
};
int N,M;
vector<string> field;
bool isValid(int y,int x){
return y>=0 && y<N && x>=0 && x<M;
}
public:
bool init(){
if(scanf("%d%d",&N,&M)==EOF)return false;
field.resize(N);
REP(i,N){
char buf[1024];
scanf("%s",buf);
field[i] = string(buf);
}
return true;
}
void solve(){
int sy,sx,gy,gx;
REP(y,N)REP(x,M){
if(field[y][x]=='s'){
sy = y;
sx = x;
}
if(field[y][x]=='g'){
gy = y;
gx = x;
}
}
vector<long double> pre(4*N*M,1);
REP(i,4*N*M-1)pre[i+1] = pre[i]*0.99;
vector<vector<long double> > used(N,vector<long double>(M,-2));
priority_queue<Node> que;que.push(Node(sy*M+sx,0,100));
while(!que.empty()){
Node n = que.top();que.pop();
int cy = n.next/M;
int cx = n.next%M;
used[cy][cx] = n.cost;

const int DY[] = {-1,0,1,0};
const int DX[] = {0,1,0,-1};
REP(i,4){
int ny = cy+DY[i];
int nx = cx+DX[i];
if(!isValid(ny,nx))continue;
long double cost = field[ny][nx]-'0';
cost *= pre[n.sec+1];
if(field[ny][nx]=='g')cost = 100;
cost = min(cost,n.cost);
if(used[ny][nx]<cost && field[ny][nx]!='#'){
que.push(Node(ny*M+nx,n.sec+1,cost));
}
}
}
if(used[gy][gx]<-1)printf("-1\n");
else printf("%.9f\n",(double)used[gy][gx]);
}
};

int main(){
C solver;
while(solver.init()){
solver.solve();
}
return 0;
}```

#### Submission Info

Submission Time 2012-05-27 20:49:31+0900 C - 暗闇帰り道 nel215 C++ (G++ 4.6.4) 0 2053 Byte WA 5035 ms 151848 KB

#### Compile Error

```./Main.cpp: In member function ‘bool C::init()’:
./Main.cpp:45:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
```

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 20 WA × 39 TLE × 4 MLE × 1
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 788 KB
00_mini_02.txt AC 22 ms 800 KB
00_mini_03.txt AC 22 ms 792 KB
00_mini_04.txt AC 22 ms 780 KB
00_mini_05.txt AC 23 ms 732 KB
00_sample_01.txt AC 23 ms 736 KB
00_sample_02.txt AC 22 ms 792 KB
01_rnd_01.txt WA 650 ms 24428 KB
01_rnd_02.txt WA 259 ms 12012 KB
01_rnd_03.txt WA 73 ms 3360 KB
01_rnd_04.txt WA 93 ms 4604 KB
01_rnd_05.txt WA 37 ms 2068 KB
01_rnd_06.txt WA 28 ms 1304 KB
01_rnd_07.txt WA 56 ms 3196 KB
01_rnd_08.txt WA 197 ms 11884 KB
01_rnd_09.txt WA 258 ms 16116 KB
01_rnd_10.txt WA 209 ms 13432 KB
01_rnd_11.txt WA 132 ms 9292 KB
01_rnd_12.txt WA 88 ms 6660 KB
01_rnd_13.txt WA 31 ms 1812 KB
01_rnd_14.txt WA 138 ms 12540 KB
01_rnd_15.txt WA 91 ms 8568 KB
01_rnd_16.txt AC 55 ms 5508 KB
01_rnd_17.txt AC 65 ms 7932 KB
01_rnd_18.txt AC 24 ms 1808 KB
01_rnd_19.txt AC 32 ms 4216 KB
01_rnd_20.txt AC 24 ms 1816 KB
02_maxrnd_01.txt WA 766 ms 24808 KB
02_maxrnd_02.txt WA 760 ms 28912 KB
02_maxrnd_03.txt WA 632 ms 24764 KB
02_maxrnd_04.txt WA 586 ms 24812 KB
02_maxrnd_05.txt WA 526 ms 24816 KB
02_maxrnd_06.txt WA 497 ms 24816 KB
02_maxrnd_07.txt WA 459 ms 24812 KB
02_maxrnd_08.txt WA 465 ms 24804 KB
02_maxrnd_09.txt WA 387 ms 22768 KB
02_maxrnd_10.txt WA 352 ms 22760 KB
02_maxrnd_11.txt WA 330 ms 22764 KB
02_maxrnd_12.txt WA 292 ms 21748 KB
02_maxrnd_13.txt WA 266 ms 21720 KB
02_maxrnd_14.txt WA 244 ms 21240 KB
02_maxrnd_15.txt WA 209 ms 20980 KB
02_maxrnd_16.txt WA 180 ms 20992 KB
02_maxrnd_17.txt WA 136 ms 20732 KB
02_maxrnd_18.txt AC 65 ms 20604 KB
02_maxrnd_19.txt AC 65 ms 20604 KB
03_hard_01.txt TLE 5034 ms 24804 KB
03_hard_02.txt TLE 5035 ms 37084 KB
03_hard_03.txt AC 106 ms 20600 KB
03_hard_04.txt AC 111 ms 20600 KB
03_hard_05.txt TLE 5034 ms 24812 KB
03_hard_06.txt TLE 5033 ms 24940 KB
03_hard_07.txt AC 86 ms 20600 KB
03_hard_08.txt AC 86 ms 20600 KB
04_open_01.txt MLE 2420 ms 151848 KB
04_open_02.txt WA 791 ms 24812 KB
05_minihard_01.txt WA 25 ms 920 KB
05_minihard_02.txt WA 67 ms 1452 KB
05_minihard_03.txt AC 23 ms 788 KB
05_minihard_04.txt AC 24 ms 796 KB
05_minihard_05.txt WA 23 ms 920 KB
05_minihard_06.txt WA 35 ms 920 KB
05_minihard_07.txt WA 22 ms 824 KB
05_minihard_08.txt WA 22 ms 792 KB