結果

問題 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;
    
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0