oj.uz

답안 #786147

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786147 2023-07-18T04:55:39 Z christinelynn Jakarta Skyscrapers (APIO15_skyscraper) C++17
0 / 100
 1 ms 980 KB 
#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({a[1].fi,0});
  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
*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 1 ms 980 KB Output isn't correct
3 Halted 0 ms 0 KB -