結果

問題 No.1638 Robot Maze
ユーザー madokamadoka
提出日時 2021-08-07 07:28:53
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 3,037 bytes
コンパイル時間 1,516 ms
コンパイル使用メモリ 170,016 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-17 11:11:01
合計ジャッジ時間 7,420 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 RE -
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 WA -
testcase_08 AC 2 ms
6,940 KB
testcase_09 WA -
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 AC 1 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/********include********/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
//#include <atcoder/all>

/***/
//#include <iomanip>
//#include <cmath>
#include <bits/stdc++.h>



#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define rrep(i,x) for(long long i=x-1;i>=0;i--)
#define rrepn(i,x) for(long long i=x;i>1;i--)
#define REP(i,n,x) for(long long i=n;i<x;i++)
#define REPN(i,n,x) for(long long i=n+1;i<x;i++)

#define pr printf
#define re return
#define mod 1000000007
//#define mod 998244353
#define inf  INT_MAX//19桁
#define INF 1e18+5//19桁
const double PI=3.14159265358979323846;
#define fi first
#define se second
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define all(x) (x).begin(),(x).end()

typedef long long int ll;
typedef pair<long long, long long> P;

struct edge{double to, cost;};
ll V;
#define MAX_V 901
//vector<edge>G[MAX_V];
vector<edge>G[MAX_V];
double d[MAX_V];

	


void back_pri_dijkstra(int s){
	priority_queue<P,vector<P>,greater<P>>que;
	fill(d,d+V,INF);
	d[s]=0;
	que.push(P(0,s));
	
	while(!que.empty()){
		P p=que.top();
		que.pop();
		int v=p.second;
		if(d[v]<p.first)continue;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(d[(ll)e.to]>d[v]+e.cost){
				d[(ll)e.to]=d[v]+e.cost;
				que.push(P(d[(ll)e.to],e.to));
			}
		}
	}
}

vector<string> masu(1005);


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll H,W;
	ll U,D,R,L,K,P;
	
	ll sh,sw,th,tw;
	cin>>H>>W;
	cin>>U>>D>>R>>L>>K>>P;
	cin>>sw>>sh>>tw>>th;
	for(ll i=1;i<=H;i++){
		cin>>masu[i];
	}
	for(ll i=1;i<=H*W;i++){
		//if(masu[(i)/W+1][(i)%W]=='#')continue;
		if(i%W!=1){
			if(masu[(i-1)/W+1][(i-1)%(W+1)]=='.'){
				G[i].push_back({(double)i-1,(double)L});
			}
			else if(masu[(i-1)/W+1][(i-1)%(W+1)]=='@'){
				G[i].push_back({(double)i-1,(double)P});
			}
		}
		if(i%W!=0){
			if(masu[(i-1)/W+1][(i+1)%(W+1)]=='.'){
				G[i].push_back({(double)i+1,(double)R});
			}
			else if(masu[(i-1)/W+1][(i+1)%(W+1)]=='@'){
				G[i].push_back({(double)i+1,(double)P});
			}
		}
		if(i-H>0){
			if(masu[(i-H-1)/W+1][(i)%(W+1)]=='.'){
				G[i].push_back({(double)i-H,(double)U});
			}
			else if(masu[(i-H-1)/W+1][(i)%(W+1)]=='@'){
				G[i].push_back({(double)i-H,(double)P});
			}
		}
		if(i+H<=H*W){
			if(masu[(i+H-1)/W+1][(i)%(W+1)]=='.'){
				G[i].push_back({(double)i+H,(double)D});
			}
			else if(masu[(i+H-1)/W+1][(i)%(W+1)]=='@'){
				G[i].push_back({(double)i+H,(double)P});
			}
		}
	}
	for(ll i=1;i<=900;i++){
		d[i]=INF;
	}

	back_pri_dijkstra((sh-1)*W+sw);
	if(d[(th-1)*W+tw]<=K){
		cout<<"Yes"<<"\n";
	}
	else{
		cout<<"No"<<"\n";
	}

	re 0;
    
}
0