Submission #18929


Source Code Expand

Copy
#include <iostream>
#include <iomanip>
#include <queue>
#include <utility>
#include <string>
#include <vector>
#include <cctype>

using namespace std;
typedef pair<int, int> pii;
typedef pair<double, pii> pdpii;

const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, -1, 0, 1 };

int main(){
	cout << setiosflags(ios::fixed) << setprecision(9);
	int N, M;
	cin >> N >> M;
	vector<string> field(N);
	int sx, sy, gx, gy;
	for(int i = 0; i < N; ++i){
		cin >> field[i];
		for(int j = 0; j < M; ++j){
			if(field[i][j] == 's'){
				sx = j; sy = i;
			}else if(field[i][j] == 'g'){
				gx = j; gy = i;
			}
		}
	}
	vector< vector<double> > optimal(N, vector<double>(M, -1.0));
	priority_queue<pdpii> pq;
	pq.push(pdpii(1e20, pii(gx, gy)));
	while(!pq.empty()){
		pdpii p = pq.top();
		pii pp = p.second;
		pq.pop();
		if(optimal[pp.second][pp.first] > p.first){ continue; }
		optimal[pp.second][pp.first] = p.first;
		if(pp.second == sy && pp.first == sx){ break; }
		double sa = p.first * 0.99;
		for(int i = 0; i < 4; ++i){
			int y = pp.second + dy[i], x = pp.first + dx[i];
			if(y < 0 || y >= N || x < 0 || x >= M){ continue; }
			if(field[y][x] == '#'){ continue; }
			double s = sa;
			if(isdigit(field[y][x])){
				s = min(s, static_cast<double>(field[y][x] - '0'));
			}
			if(optimal[y][x] < s){
				optimal[y][x] = s;
				pq.push(pdpii(s, pii(x, y)));
			}
		}
	}
	if(optimal[sy][sx] < 0.0){
		cout << "-1" << endl;
	}else{
		cout << optimal[sy][sx] << endl;
	}
	return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User logicmachine
Language C++ (G++ 4.6.4)
Score 100
Code Size 1546 Byte
Status AC
Exec Time 96 ms
Memory 3240 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 64
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 26 ms 780 KB
00_mini_02.txt AC 26 ms 780 KB
00_mini_03.txt AC 25 ms 784 KB
00_mini_04.txt AC 23 ms 868 KB
00_mini_05.txt AC 23 ms 780 KB
00_sample_01.txt AC 24 ms 780 KB
00_sample_02.txt AC 23 ms 784 KB
01_rnd_01.txt AC 62 ms 2564 KB
01_rnd_02.txt AC 40 ms 1740 KB
01_rnd_03.txt AC 27 ms 1016 KB
01_rnd_04.txt AC 32 ms 1160 KB
01_rnd_05.txt AC 22 ms 904 KB
01_rnd_06.txt AC 24 ms 868 KB
01_rnd_07.txt AC 23 ms 1036 KB
01_rnd_08.txt AC 39 ms 1804 KB
01_rnd_09.txt AC 61 ms 2436 KB
01_rnd_10.txt AC 54 ms 2172 KB
01_rnd_11.txt AC 46 ms 1668 KB
01_rnd_12.txt AC 34 ms 1420 KB
01_rnd_13.txt AC 28 ms 900 KB
01_rnd_14.txt AC 54 ms 2048 KB
01_rnd_15.txt AC 32 ms 1552 KB
01_rnd_16.txt AC 25 ms 1280 KB
01_rnd_17.txt AC 38 ms 1664 KB
01_rnd_18.txt AC 27 ms 936 KB
01_rnd_19.txt AC 27 ms 1160 KB
01_rnd_20.txt AC 25 ms 908 KB
02_maxrnd_01.txt AC 71 ms 3240 KB
02_maxrnd_02.txt AC 50 ms 3080 KB
02_maxrnd_03.txt AC 62 ms 3068 KB
02_maxrnd_04.txt AC 54 ms 3072 KB
02_maxrnd_05.txt AC 57 ms 3072 KB
02_maxrnd_06.txt AC 83 ms 3180 KB
02_maxrnd_07.txt AC 43 ms 3072 KB
02_maxrnd_08.txt AC 42 ms 3168 KB
02_maxrnd_09.txt AC 74 ms 3072 KB
02_maxrnd_10.txt AC 46 ms 3152 KB
02_maxrnd_11.txt AC 65 ms 3068 KB
02_maxrnd_12.txt AC 56 ms 3080 KB
02_maxrnd_13.txt AC 57 ms 3028 KB
02_maxrnd_14.txt AC 58 ms 2940 KB
02_maxrnd_15.txt AC 48 ms 3156 KB
02_maxrnd_16.txt AC 65 ms 3028 KB
02_maxrnd_17.txt AC 61 ms 2944 KB
02_maxrnd_18.txt AC 45 ms 2944 KB
02_maxrnd_19.txt AC 41 ms 2952 KB
03_hard_01.txt AC 91 ms 3072 KB
03_hard_02.txt AC 87 ms 3068 KB
03_hard_03.txt AC 76 ms 2956 KB
03_hard_04.txt AC 70 ms 3048 KB
03_hard_05.txt AC 85 ms 2948 KB
03_hard_06.txt AC 90 ms 3072 KB
03_hard_07.txt AC 71 ms 3032 KB
03_hard_08.txt AC 77 ms 3044 KB
04_open_01.txt AC 96 ms 2944 KB
04_open_02.txt AC 89 ms 3152 KB
05_minihard_01.txt AC 24 ms 780 KB
05_minihard_02.txt AC 24 ms 780 KB
05_minihard_03.txt AC 25 ms 784 KB
05_minihard_04.txt AC 26 ms 784 KB
05_minihard_05.txt AC 24 ms 776 KB
05_minihard_06.txt AC 24 ms 780 KB
05_minihard_07.txt AC 22 ms 780 KB
05_minihard_08.txt AC 23 ms 776 KB