Submission #131874

#	Time	Username	Problem	Language	Result	Execution time	Memory
131874		asifthegreat	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	3 ms	1144 KiB

skyscraper

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N = 30003;

struct node{
	int at,cost;
	node(int a, int b){
		at = a,cost = b;
	}
};

bool operator<(node A,node B){
	return A.cost > B.cost;
}

vector<pii>edges,graph[N];
int dist[N];

int dijkstra(int s,int n)
{
	priority_queue<node>pq;
	for(int i = 0; i < n;i++)dist[i] = 999999999;
	dist[s] = 0;
	pq.push(node(s,0));
	while(!pq.empty()){
		node u = pq.top();
		//printf("%d\n",u.at);
		pq.pop();
		if(u.cost != dist[u.at])continue;
		for(pii e: graph[u.at]){
			//printf("%d: %d -- %d,%d\n",u.at,e.first,dist[e.first],u.cost+e.second);
			if(dist[e.first] > u.cost+e.second){
				dist[e.first] = u.cost+e.second;
				pq.push(node(e.first,dist[e.first]));
			}
		}
		//exit(0);
	}
	return dist[1];
}

int main(int argc, char const *argv[])
{
	int n,m,b,a;
	scanf("%d%d",&n,&m);
	for(int i = 0; i < m;i++){
		scanf("%d%d",&a,&b);
		int x = 1;
		while(a+b*x < n){
			graph[a].push_back({a+b*x,x});
			x++;
		}
		x = 1;
		while(a-b*x >= 0){
			graph[a].push_back({a-b*x,x});
			x++;
		}
	}
	int k = dijkstra(0,n);
	if(k == 999999999)printf("-1\n");
	else printf("%d\n",k);
	return 0;
}

/*cout << "From 0:\n";
	for(pair<int,int> x: graph[0]){
		cout << x.first << " " << x.second << "\n";
	}cout << endl;
	cout << "From 1:\n";
	
	for(pair<int,int> x: graph[1]){
		cout << x.first << " " << x.second << "\n";
	}cout << endl;
	cout << "From 2:\n";

	for(pair<int,int> x: graph[2]){
		cout << x.first << " " << x.second << "\n";
	}cout << endl;
	cout << "From 3:\n";

	for(pair<int,int> x: graph[3]){
		cout << x.first << " " << x.second << "\n";
	}cout << endl;
	cout << "From 4:\n";
	for(pair<int,int> x: graph[4]){
		cout << x.first << " " << x.second << "\n";
	}cout << endl;*/

Compilation message (stderr)

skyscraper.cpp: In function 'int main(int, const char**)':
skyscraper.cpp:47: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:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~

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