Submission #1025580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025580		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	12 / 100	3 ms	8540 KiB

adventure

#include <bits/stdc++.h>

using namespace std;
const long long MAX=250010;
vector<pair<long long,long long> > graph[MAX];
long long n,m;
char mat[501][501];
long long dist[MAX];
bool vis[MAX];
long long get(long long i, long long j)
{
    return i*m+j;
}
struct node
{
    long long idx,cost;
    node() {};
    node(long long i, long long c)
    {
        idx=i;
        cost=c;
    }
    bool operator< (const node &tmp)const
    {
        return cost>tmp.cost;
    }
};
long long dijkstra(long long si, long long sj)
{
    priority_queue<node> q;
    for(long long i=0; i<n*m; i++)
    {
        vis[i]=false;
        dist[i]=INT_MAX;
    }
    q.push(node{si,0});
    dist[si]=0;
    while(!q.empty())
    {
        auto curr=q.top();
        q.pop();
        if(vis[curr.idx])continue;
        vis[curr.idx]=true;
        if(curr.idx==sj)return dist[curr.idx];
        for(long long i=0; i<graph[curr.idx].size(); i++)
        {
            long long neighbour=graph[curr.idx][i].first;
            long long val=graph[curr.idx][i].second;
            if(dist[neighbour]>curr.cost+val)
            {
                dist[neighbour]=curr.cost+val;
                q.push(node{neighbour,dist[neighbour]});
            }
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(long long i=0; i<n; i++)
    {
        for(long long j=0; j<m; j++)
        {
            cin>>mat[i][j];
        }
    }
    for(long long i=0; i<n; i++)
    {
        for(long long j=0; j<m; j++)
        {
            if(mat[i][j]=='X')continue;
            if(i+1<n)
            {
                long long a=get(i,j);
                long long b=get(i+1,j);
                if(mat[i][j]=='S')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='E')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='N')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='W')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
            if(j+1<m)
            {

                long long a=get(i,j);
                long long b=get(i,j+1);
                if(mat[i][j]=='E')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='N')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='W')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='S')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
            if(j-1>=0)
            {
                long long a=get(i,j);
                long long b=get(i,j-1);
                if(mat[i][j]=='W')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='S')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='E')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='N')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
            if(i-1>=0)
            {
                long long a=get(i,j);
                long long b=get(i-1,j);
                if(mat[i][j]=='N')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='W')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='S')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='E')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
        }
    }
    long long res=dijkstra(0,get(n-1,n-1));
    if(res==INT_MAX)res=-1;
    cout<<res<<endl;
    return 0;
}

Compilation message (stderr)

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

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