제출 #1290147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290147		kubinsgk8	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	36 / 100	274 ms	327680 KiB

skyscraper

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

//_______________________________________________

const int N=3e4+2;

long long dp1[N];
long long dp2[N];

long long n, m;


vector<pair<int, long long>> a[N];

struct bg
{
    int toanha, jump;

};

bg b[N];


//_______________________________________________

void bfs(int dinh, long long dp[])
{
    for(int i=0; i<n; i++)dp[i]=INT_MAX;

    dp[dinh]=0;

    queue<int> qu;
    qu.push(dinh);

    while(qu.size()!=0)
    {
        int temp=qu.front(); qu.pop();

        for(auto it: a[temp])
        {
            if(dp[it.first]>dp[temp]+it.second)
            {
                dp[it.first]=dp[temp]+it.second;
                qu.push(it.first);
            }
        }
    }

}



int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        cin>>b[i].toanha>>b[i].jump;
    }


    for(int i=1; i<=m; i++)
    {
        int tam=b[i].jump;

        while (b[i].toanha+tam<n)
        {
            a[b[i].toanha].push_back({b[i].toanha+tam, tam/b[i].jump});
            tam+=b[i].jump;

        }

        tam=b[i].jump;

      while (b[i].toanha-tam>=0)
        {
            a[b[i].toanha].push_back({b[i].toanha-tam, tam/b[i].jump});
            tam+=b[i].jump;

        }
    }



//    for(int i=0; i<n; i++)
//
//    {
//        for(auto it:a[i])cout<<it.first<<" "<<it.second<<"    ";
//
//        cout<<endl;
//    }

    bfs(b[1].toanha, dp1);

   // bfs(b[2].toanha, dp2);

    long long ans=INT_MAX;

 //   for(int i=0; i<n; i++)ans=min(ans, dp1[i]+dp2[i]);


    ans=dp1[b[2].toanha];

    if(ans==INT_MAX)cout<<-1;

    else cout<<ans;

    return 0;
}

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