| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1288095 | lambd47 | Jakarta Skyscrapers (APIO15_skyscraper) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
void solve(){
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>> adj(n);
vector<int> pos(n);
vector<int> pulo(n);
L(i,0,n-1)cin>>pos[i]>>pulo[i];
auto dist=[&](int i, int j)->int{
if(abs(pos[i]-pos[j])%pulo[i])return -1;
return abs(pos[i]-pos[j])/pulo[i];
};
L(i,0,n-1){
L(j,0,n-1){
if(i==j)continue;
if(dist(i,j)==-1)continue;
adj[i].push_back({j,dist[i][j]});
}
}
const int MOD=1e9+7;
vector<int> dp(n,MOD);
dp[0]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({dp[0],0});
while(!pq.empty()){
auto [d,v]=pq.top();
pq.pop();
if(d!=dp[v])continue;
for(auto [node,w]:adj[v]){
if(dp[node]>dp[v]+w){
dp[node]=dp[v]+w;
pq.push({dp[node],node});
}
}
}
cout<<((dp[1]==MOD)?-1:dp[1]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
solve();
}
//fazer um pseudo floyd warshal, na vdd da pra construir um super clique com as distancias de cad