| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1271998 | pvb.tunglam | Jakarta Skyscrapers (APIO15_skyscraper) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define hash _hash_
#define left _left_
#define y1 _y1_
using namespace std;
using ll = long long;
const ll oo = 1e18;
/*----------- I alone decide my fate! ----------*/
/* Chiec den ong sao, sao 5 canh tuoi mau */
int N, M;
int B[30009], P[30009];
vector<pair<int,int>> adj[30009];
ll dista[30009];
void Dijkstra() {
for (int i = 0; i < M; i++) dista[i] = oo;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
dista[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
auto [cost, u] = pq.top();
pq.pop();
if (cost != dista[u]) continue;
if (u == 1) {
cout << cost;
return;
}
for (auto [v, w] : adj[u]) {
if (dista[v] > cost + w) {
dista[v] = cost + w;
pq.push({dista[v], v});
}
}
}
cout << -1;
}
vector <int> buckets[30009];
void solve() {
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> B[i] >> P[i];
buckets[P[i]].push_back(i);
}
for (auto &bucket : buckets[p]) {
sort(bucket.begin(), bucket.end());
for (int k = 0; k+1 < bucket.size(); k++) {
int u = id[bucket[k]];
int v = id[bucket[k+1]];
int w = (bucket[k+1] - bucket[k]) / p;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
Dijkstra();
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
solve();
return 0;
}
/*
How can you see into my eyes, like open doors?
Leading you down into my core, where I've become so numb
Without a soul, my spirit's sleeping somewhere cold
Until you find it here and bring it back home!
Wake me up! Wake me up inside
Cant wake up? Wake me up inside
*/