제출 #948099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948099		4QT0R	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	516 ms	8356 KiB

skyscraper

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

priority_queue<pii,vector<pii>,greater<pii>> pq;
vector<ll> doges[30002];
bool vis[30002];
ll jmp[30002];
ll odl[30002];
ll n,m,oo=1e14;

void Dijkstra(ll pos, ll kon){
	fill(odl,odl+n,oo);
	odl[pos]=0;
	pq.push({0,pos});
	ll iter;
	while(pq.size()){
		auto [d,v]=pq.top();
		pq.pop();
		if (d>odl[v])continue;
		if (v==kon)break;
		for (auto u : doges[v]) if (!vis[u]){
			vis[u]=true;
			iter=1;
			for (ll i = v+jmp[u]; i<n; i+=jmp[u]){
				if (odl[i]>d+iter){
					odl[i]=d+iter;
					pq.push({d+iter,i});
				}
				iter++;
			}
			iter=1;
			for (ll i = v-jmp[u]; i>=0; i-=jmp[u]){
				if (odl[i]>d+iter){
					odl[i]=d+iter;
					pq.push({d+iter,i});
				}
				iter++;
			}
		}
	}
	if (odl[kon]==oo)cout << "-1\n";
	else cout << odl[kon] << '\n';
}

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

	ll b,p,st,nd;
	cin >> n >> m;
	cin >> st >> jmp[1];
	doges[st].push_back(1);
	cin >> nd >> p;
	for (ll i = 2; i<m; i++){
		cin >> b >> jmp[i];
		doges[b].push_back(i);
	}
	Dijkstra(st,nd);
}

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