제출 #106721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106721		brcode	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	63 ms	21060 KiB

skyscraper

#include <iostream>
#include <queue>
using namespace std;
queue<pair<int,int>> q1;
const int MAXN = 2010;
vector<int> v1[MAXN];
bool visited[MAXN];
int dp[MAXN][MAXN];
int target;
bool visited2[MAXN][MAXN];
int first,jump;
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int b,p;
        cin>>b>>p;
        if(i== 0){
            first = b;
            jump = p;
        }
        if(i == 1){
            target = b;
        }
        v1[b].push_back(p);
    }
    q1.push(make_pair(first,jump));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]= 1e9;
        }
    }
    dp[first][jump] = 0;
    
    while(!q1.empty()){
        auto hold = q1.front();
        int skyscraper = hold.first;
        int hop = hold.second;
       
        q1.pop();
        
        if(skyscraper == target){
            
            cout<<dp[skyscraper][hop]<<endl;
            return 0;
        }
        if(visited2[skyscraper][hop]){
            continue;
        }
     //   cout<<dp[skyscraper][hop]<<" "<<skyscraper<<" "<<hop<<" "<<endl;
        visited2[skyscraper][hop] = true;
        if(skyscraper-hop>=0){
            if(dp[skyscraper-hop][hop]>=dp[skyscraper][hop]+1){
                dp[skyscraper-hop][hop] = dp[skyscraper][hop]+1;
                q1.push(make_pair(skyscraper-hop,hop));
            }
        }
        if(skyscraper+hop<=n){
            if(dp[skyscraper+hop][hop]>=dp[skyscraper][hop]+1){
                dp[skyscraper+hop][hop] = dp[skyscraper][hop]+1;
                q1.push(make_pair(skyscraper+hop,hop));
            }
        }
        if(!visited[skyscraper]){
            visited[skyscraper] =true;
            for(int x:v1[skyscraper]){
                if(x!=hop){
                    if(skyscraper-x>=0){
                        if(dp[skyscraper-x][x]>=dp[skyscraper][hop]+1){
                            dp[skyscraper-x][x] = dp[skyscraper][hop]+1;
                            q1.push(make_pair(skyscraper-x,x));
                        }
                    }
                    if(skyscraper+x<=n){
                        if(dp[skyscraper+x][x]>=dp[skyscraper][hop]+1){
                            dp[skyscraper+x][x] = dp[skyscraper][hop]+1;
                            q1.push(make_pair(skyscraper+x,x));
                        }
                    }
                }
            }
        }
        
    }
    cout<<-1<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43