제출 #249415

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

skyscraper

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#define INF 200000000
#define maxV 30005

int N,M;
pair<int,int> doge[maxV];
int dist[maxV];
int visited[maxV];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0;i<M;i++){
        cin>>doge[i].first>>doge[i].second;
        dist[i]=INF;
    }
    //dijkstra's
    priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > >pq;
    dist[0]=0;
    pq.push( make_pair(0,0) );
    while(!pq.empty()){
        int cn=pq.top().second;
        pq.pop();
        if(visited[cn]==true) continue;
        visited[cn]=true;
        for(int i=0;i<N;i++){
            int dtn=abs(doge[cn].first-doge[i].first);
            if(dtn%doge[cn].second==0){
                if(dist[cn]+(dtn/doge[cn].second)<dist[i]){
                    dist[i]=dist[cn]+(dtn/doge[cn].second);
                    pq.push(make_pair(dist[i],i));
                }
            }
        }

    }
    if(dist[1]==INF){
        cout<<-1<<'\n';
    }else{
        cout<<dist[1]<<'\n';
    }

    return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

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