제출 #315709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
315709		Benmath	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	149 ms	40944 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
long long int INF=1e15;
long long int dist[300000];
vector<vector<pair<int,int>>> adjl;
void dijsktra(int s,long long int *dist,vector<vector<pair<int,int>>>adjl){
   using pii=pair<int,int>;
   priority_queue<pii,vector<pii>,greater<pii>>pq;
   dist[s]=0;
   pq.push({0,s});
   while(!pq.empty()){
      pii trenutni=pq.top();
      pq.pop();
      int d=trenutni.first;
      int u=trenutni.second;
      if(d>dist[u]) continue;
      for(int i=0;i<adjl[u].size();i++){
         pii v=adjl[u][i];
        
         if(dist[u]+v.first <dist[v.second]){
            dist[v.second]=dist[u]+v.first;
             pq.push({dist[v.second],v.second});
      }
   }
}
}
int trans(char a1,char a2){
   int x1;
   int x2;
   if(a1=='S'){
      x1=1;
      
   }
   if(a1=='W'){
      x1=2;
   }
   if(a1=='N'){
      x1=3;
   }
   if(a1=='E'){
      x1=4;
   }  if(a2=='S'){
      x2=1;
      
   }
   if(a2=='W'){
      x2=2;
   }
   if(a2=='N'){
      x2=3;
   }
   if(a2=='E'){
      x2=4;
   }
 
   if(x2>=x1){
      return (x2-x1);
   }else{
      return (x2+4-x1);
   }
   
}
int main(){
  int n,m;
  cin>>n>>m;
  adjl.resize(n*m);

  char matrica[n][m];
  int a[n][m];
  int brojac=0;
  for(int i=0;i<n;i++){
     string s;
     cin>>s;
     for(int j=0;j<m;j++){
   matrica[i][j]=s[j];
        a[i][j]=brojac;
        brojac++;
     }
  }
  brojac=0;

  for(int i=0;i<n;i++){
     for(int j=0;j<m;j++){
        dist[brojac]=INF;
     
        brojac++;
        if(matrica[i][j]!='X'){
        if(i>0){
           adjl[a[i][j]].push_back(make_pair(trans(matrica[i][j],'N'),a[i-1][j]));
        }
        if(j>0){
             adjl[a[i][j]].push_back(make_pair(trans(matrica[i][j],'W'),a[i][j-1]));
        }
        if(i<(n-1)){
       
             adjl[a[i][j]].push_back(make_pair(trans(matrica[i][j],'S'),a[i+1][j]));
        } 
       
        if(j<(m-1)){
             adjl[a[i][j]].push_back(make_pair(trans(matrica[i][j],'E'),a[i][j+1]));
        }
     }
  }
  } 
  dijsktra(0,dist,adjl);

  if(dist[n*m-1]==INF){
   cout<<-1;
  }else{
     cout<<dist[n*m-1];
  }
}

컴파일 시 표준 에러 (stderr) 메시지

adventure.cpp: In function 'void dijsktra(int, long long int*, std::vector<std::vector<std::pair<int, int> > >)':
adventure.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |       for(int i=0;i<adjl[u].size();i++){
      |                   ~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50