Submission #642042

#	Time	Username	Problem	Language	Result	Execution time	Memory
642042		Theo830	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	102 ms	21436 KiB

adventure

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
priority_queue<ii,vector<ii>, greater<ii>> pq;
#define INF 100000000
vector<vii> graph;
vi dist;

void dijkstra(int s){
    dist[s] = 0;
    pq.push(ii(0,s));

    while(!pq.empty()){
        ii front = pq.top();
        pq.pop();
        int w = front.first;
        int u = front.second;

        if(w>dist[u]){
            continue;
        }

        for(int i=0; i<graph[u].size(); i++){
            ii v = graph[u][i];

            if(dist[u]+v.second<dist[v.first]){
                dist[v.first] = dist[u]+v.second;
                pq.push(ii(dist[v.first], v.first));
            }
        }
    }
}

int main(){
    int n,m;
    cin >> m >> n;

    graph.assign(m*n, vii());
    dist.assign(m*n,INF);

    char arr[m][n];

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
           cin >> arr[i][j];
        }
    }

    vector<map<char,int>> mp = {{{'N',0},{'E',3},{'S',2},{'W',1}}, {{'N',1},{'E',0},{'S',3},{'W',2}}, {{'N',2},{'E',1},{'S',0},{'W',3}} , {{'N',3},{'E',2},{'S',1},{'W',0}}};
    int k = 0;

    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
          if(j-1>=0 && arr[i][j]!='X') graph[k].push_back(ii(k-1,mp[3][arr[i][j]]));
          if(j+1<n && arr[i][j] !='X')  graph[k].push_back(ii(k+1,mp[1][arr[i][j]]));
          if(i-1>=0 && arr[i][j] !='X') graph[k].push_back(ii(k-n,mp[0][arr[i][j]]));
          if(i+1<m && arr[i][j]!='X')  graph[k].push_back(ii(k+n,mp[2][arr[i][j]]));
          k++;
        }
    }

    dijkstra(0);


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

Compilation message (stderr)

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

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