제출 #786151

#제출 시각아이디문제언어결과실행 시간메모리
786151devariaotaJakarta Skyscrapers (APIO15_skyscraper)C++17
0 / 100
1 ms980 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define endl "\n" #define pii pair<ll,ll> #define pb push_back #define vi vector<ll> #define pque priority_queue #define pqueg priority_queue<ll,vector<ll>,greater<ll>> #define que queue<ll> #define FOR(m,i,n) for(int i=(m); i<=(n); i++) #define FORM(m,i,n) for(int i=(m); i>=(n); i--) ll n,m; pii a[30300]; vector<pii> adj[30300]; priority_queue<pii,vector<pii>,greater<pii>> pq; ll dist[30030]; bool vis[30030]; ll temp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; FOR(1,i,m) { cin >> a[i].fi >> a[i].se; if(i == 2) { temp = a[i].fi; } } sort(a+1,a+m+1); FOR(1,i,m) { FOR(1,j,m) { if(a[i].fi == a[j].fi) continue; if(abs(a[i].fi - a[j].fi) % a[i].se == 0) { adj[a[i].fi].pb({a[j].fi,abs(a[i].fi - a[j].fi) / a[i].se}); } } } pq.push({0,a[1].fi}); FOR(1,i,n) { dist[i] = 1e9; } while(!pq.empty()) { pii x = pq.top(); pq.pop(); for(auto i : adj[x.se]) { // if(!vis[i.fi]) { // vis[i.fi] = true; if(dist[i.fi] > dist[x.se] + i.se) { dist[i.fi] = dist[x.se] + i.se; pq.push({dist[i.fi],i.fi}); } // } } } if(dist[temp] == 1e9) { cout << -1 << endl; } else { cout << dist[1] << endl; } } /* 5 3 0 2 1 1 4 1 5 3 0 2 1 3 2 2 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...