제출 #1280892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280892		SSKMF	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	1 ms	580 KiB

skyscraper

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

pair <int , int> sir[30001];
int distanta[30001];
bool vizitat[30001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri_1 , numar_noduri_2;
    cin >> numar_noduri_1 >> numar_noduri_2;

    for (int indice = 1 ; indice <= numar_noduri_1 ; indice++)
        { distanta[indice] = INT32_MAX; }

    for (int indice = 1 ; indice <= numar_noduri_2 ; indice++)
        { cin >> sir[indice].first >> sir[indice].second; sir[indice].first++; }
    
    distanta[sir[1].first] = 0;
    while (true)
    {
        int inceput = -1;
        for (int indice = 1 ; indice <= numar_noduri_2 ; indice++) {
            if (!vizitat[indice] && (inceput == -1 || distanta[sir[inceput].first] > distanta[sir[indice].first]))
                { inceput = indice; }
        }

        if (distanta[inceput] == INT32_MAX) 
            { cout << "-1"; break; }

        if (inceput == 2)
            { cout << distanta[sir[2].first]; break; }

        vizitat[inceput] = true;
        for (int indice = sir[inceput].first ; indice <= numar_noduri_1 ; indice += sir[inceput].second)
            { distanta[indice] = min(distanta[indice] , distanta[sir[inceput].first] + (indice - sir[inceput].first) / sir[inceput].second); }
            
        for (int indice = sir[inceput].first - sir[inceput].second ; indice > 0 ; indice -= sir[inceput].second)
            { distanta[indice] = min(distanta[indice] , distanta[sir[inceput].first] + (sir[inceput].first - indice) / sir[inceput].second); }
    }
    
    return 0;
}

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