제출 #1264178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264178		elotelo966	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	3 ms	4936 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 200005

int n,m;

int dizi[lim][2];

vector<pair<int,int>> v[lim];

int vis[lim],dist[lim];

inline void dij(){
	for(int i=1;i<=m;i++){
		vis[i]=0;
		dist[i]=LLONG_MAX;
	}
	dist[1]=0;
	priority_queue<pair<int,int>> pq;
	pq.push({0,1});
	while(pq.size()){
		int node=pq.top().se;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		for(auto go:v[node]){
			if(dist[node]!=LLONG_MAX && dist[go.fi]>dist[node]+go.se){
				dist[go.fi]=dist[node]+go.se;
				pq.push({-dist[go.fi],go.fi});
			}
		}
	}
}

int32_t main(){
	faster
	cin>>n>>m;
	
	for(int i=1;i<=m;i++){
		cin>>dizi[i][0]>>dizi[i][1];
	}
	
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j)continue;
			int tut=abs(dizi[i][0]-dizi[j][0]);
			if(tut%dizi[i][1])continue;
			v[i].pb({j,tut/dizi[i][1]});
		}
	}
	
	dij();
	
	cout<<dist[2]<<'\n';
	
	return 0;
}

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