Submission #335224

#	Time	Username	Problem	Language	Result	Execution time	Memory
335224		hivakarami	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	1 ms	1024 KiB

skyscraper

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double doublel;
#define f first
#define s second
 
const int N = 30000 + 100;
const ll base = 313;
const ll mod = 1e9 + 9;	
const ll inf = 1e17;	

set<pair<ll, int>> s;
ll dis[N];
vector<pair<int, int>> adj[N];

int n, m, b, p;

void dij(int u)
{
	for(int i = 0; i < n; i++)
		dis[i] = inf;
	dis[u] = 0;
	for(int i = 0; i < n; i++)	
		s.insert({dis[i], i});
	while(!s.empty())
	{
		int x = s.begin() -> s;
		s.erase(s.begin());
		
		for(auto y : adj[x])
		{
			if(dis[y.f] > dis[x] + y.s)
			{
				s.erase({dis[y.f], y.f});
				dis[y.f] = dis[x] + y.s;
				s.insert({dis[y.f], y.f});
			}
		}
	}	
		
		
}





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

	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> b >> p;
		for(int i = b+p; i <= n; i += p)
		{
			adj[b].push_back({i, (i-b)/p});
			//cout << i << ' ' << b << ' ' << (i-b)/p << endl; 
		}
			
		for(int i = b-p; i >= 0; i -= p)
		{
			adj[b].push_back({i, (b-i)/p});
			//cout << i << ' ' << b << ' ' << (b-i)/p << endl;
		}
	}
	
	dij(0);
	
	cout << dis[1] << endl;
	
	
	

    return 0;
}

 
 	
 	


/*
5 3
0 2
1 1
4 1
*/





 

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