제출 #946971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946971		AliHasanli	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	98 ms	60592 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long>>g[1000000];
int currentnode(int i,int j,int column)
{
    return i*(column+2)+j+1;
}
vector<long long>shortest_path(int source)
{
    vector<long long>answer(1000000,1000000000000000000);
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>pq;
    vector<int>used(1000000,0);
    pq.push({0,source});
    while(pq.size())
    {
        //cout<<"A"<<endl;
        int node=pq.top().second;
        long long cost=pq.top().first;
        pq.pop();
        if(used[node])continue;
        used[node]=1;
        answer[node]=cost;

        for(pair<int,long long>go:g[node])
        {
            if(used[go.first])continue;
            pq.push({go.second+cost,go.first});
        }
    }
    return answer;
}
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            char a;
            cin>>a;
            //cout<<"currentnode "<<currentnode(i,j,n)<<endl;
            if(a=='W')
            {
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-1,0});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-n-2,1});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+1,2});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+n+2,3});
            }
            else if(a=='E')
            {
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+1,0});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+n+2,1});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-1,2});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-n-2,3});
            }
            else if(a=='S')
            {
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+n+2,0});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-1,1});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-n-2,2});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+1,3});
            }
            else if(a=='N')
            {
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-n-2,0});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+1,1});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)+n+2,2});
                g[currentnode(i,j,n)].push_back({currentnode(i,j,n)-1,3});
            }
        }
    vector<long long>dis=shortest_path(n+4);
    //for(int i=1;i<=(n+2)*(m+2);i++)cout<<dis[i]<<" ";cout<<endl;
    if(dis[(n+2)*(m+2)-n-3]==1000000000000000000)cout<<-1;
    else cout<<dis[(n+2)*(m+2)-n-3];
    return 0;
}

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