제출 #15716

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15716		cki86201	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	10 / 100	0 ms	3104 KiB

skyscraper

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<queue>
using namespace std;

#define X first
#define Y second
typedef pair<int, int> Pi;
const int MX = 30003;
const int SX = 0;

priority_queue <Pi, vector<Pi>, greater<Pi> > pq;
vector <Pi> E[MX];
int n, m;
int p[MX][2];
int chk[MX][SX+4];
int len[MX];

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++){
		scanf("%d%d", p[i], p[i] + 1);
		if (p[i][1] < SX)chk[p[i][0]][p[i][1]] = 1;
	}
	for (int i = 0; i < m; i++){
		for (int j = p[i][0] + p[i][1], l = 1; j < n; j += p[i][1], l++){
			E[p[i][0]].push_back(Pi(j, l));
			if (p[i][1] < SX && chk[j][p[i][1]])break;
		}
	}
	for (int i = 0; i < m; i++){
		for (int j = p[i][0] - p[i][1], l = 1; j >= 0; j -= p[i][1], l++){
			E[p[i][0]].push_back(Pi(j, l));
			if (p[i][1] < SX && chk[j][p[i][1]])break;
		}
	}
	pq.push(Pi(p[0][0], 0));
	for (int i = 0; i < n; i++)len[i] = 1e9;
	len[p[0][0]] = 0;
	while (!pq.empty()){
		Pi t = pq.top();
		pq.pop();
		if (len[t.Y] != t.X)continue;
		if (t.Y == p[1][0])break;
		for (int i = 0; i < (int)E[t.Y].size(); i++){
			Pi &w = E[t.Y][i];
			if (len[w.X] > len[t.Y] + w.Y){
				len[w.X] = len[t.Y] + w.Y;
				pq.push(Pi(len[w.X], w.X));
			}
		}
	}
	printf("%d", len[p[1][0]] == 1e9 ? -1 : len[p[1][0]]);
	return 0;
}

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