結果

問題 No.1638 Robot Maze
コンテスト
ユーザー madoka
提出日時 2021-08-07 14:47:29
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 2,957 bytes
コンパイル時間 1,556 ms
コンパイル使用メモリ 168,672 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 18:36:55
合計ジャッジ時間 3,422 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:145:21: warning: iteration 10004 invokes undefined behavior [-Waggressive-loop-optimizations]
  145 |                 d[i]=INF;
      |                     ^
main.cpp:144:21: note: within this loop
  144 |         for(ll i=1;i<=10005;i++){
      |                    ~^~~~~~~

ソースコード

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 10005
//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(10005);


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>>sh>>sw>>th>>tw;
	for(ll i=1;i<=H;i++){
		cin>>masu[i];
	}
	ll X;
	ll Y;
	for(ll i=1;i<=H*W;i++){
		Y=(i-1)/W+1;
		X=i-((Y-1)*W)-1;	
		if(masu[Y][X]=='#')continue;
		if(X-1>=0){
			if(masu[Y][X-1]=='.'){
				G[i].push_back({(double)i-1,(double)L});
			}
			else if(masu[Y][X-1]=='@'){
				G[i].push_back({(double)i-1,(double)P+L});
			}
		}
		if(X+1<W){
			if(masu[Y][X+1]=='.'){
				G[i].push_back({(double)i+1,(double)R});
			}
			else if(masu[Y][X+1]=='@'){
				G[i].push_back({(double)i+1,(double)P+R});
			}
		}
		if(Y-1>=1){
			if(masu[Y-1][X]=='.'){
				G[i].push_back({(double)i-W,(double)U});
			}
			else if(masu[Y-1][X]=='@'){
				G[i].push_back({(double)i-W,(double)P+U});
			}
		}
		if(Y+1<=H){
			if(masu[Y+1][X]=='.'){
				G[i].push_back({(double)i+W,(double)D});
			}
			else if(masu[Y+1][X]=='@'){
				G[i].push_back({(double)i+W,(double)P+D});
			}
		}
	}
	for(ll i=1;i<=10005;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