Submission #260787

#	Time	Username	Problem	Language	Result	Execution time	Memory
260787		T0p_	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	702 ms	6004 KiB

skyscraper

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

struct DJK
{
	int node;
	long long weight;
	bool operator < (const DJK & o) const
	{
		return weight > o.weight;		
	}	
};

vector<int> B[30003];
long long dis[30003];
bool visit[30003];
priority_queue<DJK> djk;

int main() 
{
	int n, m, s, e;
	scanf(" %d %d",&n,&m);
	for(int i=1, b, p ; i<=m ; i++)
	{
		scanf(" %d %d",&b,&p);
		b++;
		B[b].push_back(p);
		if(i == 1) s = b;
		if(i == 2) e = b;
	}
	for(int i=1 ; i<=n ; i++)
		dis[i] = 1e15;
	dis[s] = 0;
	djk.push({s, 0});
	while(!djk.empty())
	{
		int nown = djk.top().node;
		long long noww = djk.top().weight;
		djk.pop();
		if(visit[nown]) continue ;
		visit[nown] = true;
		if(nown == e)
		{
			printf("%lld\n",noww);
			return 0;
		}
		for(auto x : B[nown])
		{
			//left
			for(int i=1 ; nown - x*i >= 1 ; i++)
				if(dis[nown - x*i] > dis[nown] + i)
				{
					dis[nown - x*i] = dis[nown]+i;
					djk.push({nown - x*i, dis[nown - x*i]});
				}
			//right
			for(int i=1 ; nown + x*i <= n ; i++)
				if(dis[nown + x*i] > dis[nown] + i)
				{
					dis[nown + x*i] = dis[nown]+i;
					djk.push({nown + x*i, dis[nown + x*i]});
				}
		}
	}
	printf("-1\n");
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %d %d",&b,&p);
   ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:42:3: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(nown == e)
   ^~
skyscraper.cpp:34:10: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
  djk.push({s, 0});
  ~~~~~~~~^~~~~~~~

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