Submission #124072

#	Time	Username	Problem	Language	Result	Execution time	Memory
124072		RafikHachana	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	2 ms	404 KiB

skyscraper

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

vector<vector<pair<int,int> > > g;
int n,m;

void dijsktra()
{
  vector<int> dist(n,1e9);
  priority_queue<pair<int,int> , vector<pair<int,int> > , greater<pair<int,int> > > q;
  q.push({0,0});
  dist[0] = 0;
  while(!q.empty())
  {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    for(auto it:g[u])
    {
      if(dist[it.second]> d + it.first)
      {
        dist[it.second] =  d + it.first;
        q.push({dist[it.second],it.second});
      }
    }
  }
  cout<<dist[1]<<endl;
}


int main()
{
  cin>>m>>n;
  vector<int> b(n),p(n);
  for(int i=0;i<n;i++)
  {
    cin>>b[i]>>p[i];
  }
  g.resize(n);
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      if(i==j) continue;
      if(b[i]%p[i]==b[j]%p[i]) g[i].push_back({abs(b[j]-b[i])/p[i],j});
    }
  }
  dijsktra();
}

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