제출 #373801

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

skyscraper

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;

int d(int x,int y,vector<vector<pair<int,int> > >&s){
  int N=s.size();
  vector<int>dis(N,1e9);
  dis[x]=0;
  priority_queue<pair<int,int> >pq;
  pq.push(make_pair(0,x));
  while(!pq.empty()){
    int nodo=pq.top().second;
    int d=-pq.top().first;
    pq.pop();
    if(d>dis[nodo])
      continue;
    dis[nodo]=d;
    for(pair<int,int>v:s[nodo]){
      int vec=v.first;
      int dv=v.second;
      if(dis[vec]>dis[nodo]+dv){
        dis[vec]=dis[nodo]+dv;
        pq.push(make_pair(-dis[vec],vec));
      }
    }

  }
  if(dis[y]==1e9){
    return -1;
  }
  else{
    return dis[y];
  }
}

int main(){
   ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,M,B,P;
  cin>>N>>M;
  vector<vector<pair<int,int> > >s(N);
  vector<int>b(M);
  for(int i=0;i<M;i++){
  cin>>B>>P;
  b[i]=B;
  int j=B;
  int o=1,u=1;
  while(j-P>=0){
   s[B].push_back(make_pair(j-P,P*o));
    j=j-P;
    o++;
  }
   while(j+P<=N){
    s[B].push_back(make_pair(j+P,P*u));
    j=j+P;
    u++;
  }
  }
  int x=b[0];
  int y=b[1];
  cout<<d(x,y,s);
  return 0;
}

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