이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 3e4+7, inf = 1e18;
int a[N], p[N], d[N], mark[N];
vector<int> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dij(int n){
fill(d,d+n,inf);
d[a[0]] = 0;
q.push({0,a[0]});
while(q.size()){
int v = q.top().S;
q.pop();
if (v == a[1]) return;
if (mark[v]) continue;
mark[v] = 1;
for (int p : g[v]){
for(int i=v; i<n; i+=p){
if (d[i] > d[v] + (i-v)/p){
d[i] = d[v] + (i-v)/p;
q.push({d[i],i});
}
}
for(int i=v; i>=0; i-=p){
if (d[i] > d[v] + (v-i)/p){
d[i] = d[v] + (v-i)/p;
q.push({d[i],i});
}
}
}
}
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,m; cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a[i] >> p[i];
g[a[i]].pb(p[i]);
}
dij(n);
cout << (d[a[1]] == inf ? -1 : d[a[1]]) << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
skyscraper.cpp:12:28: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
12 | const int N = 3e4+7, inf = 1e18;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |