Submission #32988


Source Code Expand

Copy
#include <iostream>
#include <queue>
#include <algorithm>
#include <cctype>
#include <utility>
#include <cstdio>
using namespace std;

#define at(a,x) (a[x/502][x%502])

char mp[502][502];
double light[502][502];

int df[4] = {-502, -1, 1, 502};

typedef pair<double,int> pdi;

int main(){
	fill( *mp, *mp + sizeof mp, '#' );

	int n, m;
	cin >> n >> m;

	for( int i = 1; i <= n; ++i ){
		cin >> &mp[i][1];
		mp[i][m + 1] = '#';
	}

	int g = find( *mp, *mp + sizeof mp, 'g' ) - *mp;
	at( light, g ) = 10.0;
	priority_queue<pdi> pq;
	pq.push( pdi( 10.0, g ) );
	
	while( !pq.empty() ){
		pdi p = pq.top();
		pq.pop();
		
		if( at( mp, p.second ) == 's' ){
			printf("%.10f\n", p.first );
			return 0;
		}
		
		if( at( light, p.second ) == p.first ){
			for( int i = 0; i < 4; ++i ){
				int x = p.second + df[i];
				if( at( mp, x ) != '#' ){
					double ml = p.first * 0.99;
					if( isdigit( at( mp, x ) ) ){
						ml = min( ml, (double)(at( mp, x ) - '0') );
					}
					
					if( ml > at( light, x ) ){
						at( light, x ) = ml;
						pq.push( pdi( ml, x ) );
					}
				}
			}
		}
	}
	
	cout << "-1\n";
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User climpet
Language C++ (GCC 4.4.7)
Score 100
Code Size 1172 Byte
Status AC
Exec Time 81 ms
Memory 3064 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 23 ms 1036 KB
00_mini_02.txt AC 22 ms 1044 KB
00_mini_03.txt AC 22 ms 1016 KB
00_mini_04.txt AC 22 ms 1024 KB
00_mini_05.txt AC 22 ms 1024 KB
00_sample_01.txt AC 21 ms 1040 KB
00_sample_02.txt AC 22 ms 1020 KB
01_rnd_01.txt AC 57 ms 2676 KB
01_rnd_02.txt AC 36 ms 2172 KB
01_rnd_03.txt AC 24 ms 1272 KB
01_rnd_04.txt AC 28 ms 1664 KB
01_rnd_05.txt AC 24 ms 1280 KB
01_rnd_06.txt AC 24 ms 1180 KB
01_rnd_07.txt AC 24 ms 1276 KB
01_rnd_08.txt AC 37 ms 1832 KB
01_rnd_09.txt AC 56 ms 2552 KB
01_rnd_10.txt AC 53 ms 2820 KB
01_rnd_11.txt AC 42 ms 1920 KB
01_rnd_12.txt AC 31 ms 1660 KB
01_rnd_13.txt AC 24 ms 1152 KB
01_rnd_14.txt AC 50 ms 2296 KB
01_rnd_15.txt AC 32 ms 1796 KB
01_rnd_16.txt AC 25 ms 1172 KB
01_rnd_17.txt AC 26 ms 1024 KB
01_rnd_18.txt AC 23 ms 1272 KB
01_rnd_19.txt AC 23 ms 1052 KB
01_rnd_20.txt AC 22 ms 1176 KB
02_maxrnd_01.txt AC 62 ms 2676 KB
02_maxrnd_02.txt AC 43 ms 2044 KB
02_maxrnd_03.txt AC 54 ms 2940 KB
02_maxrnd_04.txt AC 48 ms 2552 KB
02_maxrnd_05.txt AC 54 ms 2208 KB
02_maxrnd_06.txt AC 75 ms 3064 KB
02_maxrnd_07.txt AC 36 ms 1404 KB
02_maxrnd_08.txt AC 35 ms 1532 KB
02_maxrnd_09.txt AC 70 ms 2940 KB
02_maxrnd_10.txt AC 39 ms 1912 KB
02_maxrnd_11.txt AC 61 ms 2948 KB
02_maxrnd_12.txt AC 51 ms 2168 KB
02_maxrnd_13.txt AC 50 ms 2172 KB
02_maxrnd_14.txt AC 56 ms 2564 KB
02_maxrnd_15.txt AC 43 ms 2036 KB
02_maxrnd_16.txt AC 60 ms 2936 KB
02_maxrnd_17.txt AC 57 ms 2936 KB
02_maxrnd_18.txt AC 33 ms 1392 KB
02_maxrnd_19.txt AC 32 ms 1140 KB
03_hard_01.txt AC 81 ms 2936 KB
03_hard_02.txt AC 78 ms 2940 KB
03_hard_03.txt AC 72 ms 2936 KB
03_hard_04.txt AC 72 ms 2932 KB
03_hard_05.txt AC 81 ms 2956 KB
03_hard_06.txt AC 79 ms 2932 KB
03_hard_07.txt AC 71 ms 2924 KB
03_hard_08.txt AC 71 ms 2932 KB
04_open_01.txt AC 79 ms 2944 KB
04_open_02.txt AC 80 ms 2944 KB
05_minihard_01.txt AC 21 ms 1176 KB
05_minihard_02.txt AC 22 ms 1144 KB
05_minihard_03.txt AC 22 ms 1144 KB
05_minihard_04.txt AC 21 ms 1168 KB
05_minihard_05.txt AC 22 ms 1180 KB
05_minihard_06.txt AC 22 ms 1140 KB
05_minihard_07.txt AC 22 ms 1148 KB
05_minihard_08.txt AC 22 ms 1144 KB