제출 #1110673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110673		vjudge1	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	105 ms	11600 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
const int BLOCK=226;
int m,n,s,t,u,vv;
int dp[50005];
bool check[50005][BLOCK+5];
vector<int> g[50005];
struct jakarta
{
    int v,p,w;
    jakarta(int v,int p,int w): v(v),p(p),w(w) {}
};
queue<jakarta> Q;
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=0;i<m;++i)
    {
        cin>>u>>vv;
        g[u].push_back(vv);
        if (i==0)
        {
            s=u;
        }
        if (i==1)
        {
            t=u;
        }
    }
    memset(dp,-1,sizeof dp);
    Q.emplace(s,0,0);
    while (Q.size())
    {
        jakarta hao=Q.front();
        Q.pop();
        if (hao.v<0 || hao.v>=n) continue;
        if (abs(hao.p)<BLOCK)
        {
            if (check[hao.v][abs(hao.p)]) continue;
            check[hao.v][abs(hao.p)]=1;
        }
        if (dp[hao.v]==-1)
        {
            dp[hao.v]=hao.w;
            for (auto it: g[hao.v])
            {
                Q.emplace(hao.v+it,it,hao.w+1);
                Q.emplace(hao.v-it,-it,hao.w+1);
            }
        }
        Q.emplace(hao.v+hao.p,hao.p,hao.w+1);
    }
    cout<<dp[t];
}

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