Submission #1272040

#TimeUsernameProblemLanguageResultExecution timeMemory
1272040thuhienneJakarta Skyscrapers (APIO15_skyscraper)C++20
100 / 100
544 ms43716 KiB
#include <bits/stdc++.h> using namespace std; #define end __end__ const int can = 350; int n,m,start,end; vector <int> power[30009]; int l[30009][can + 3]; struct doges { int vertice,jump,cost; bool operator < (const doges & other) const { return cost > other.cost; } }; void djt() { for (int i = 1;i <= n;i++) for (int j = 1;j <= can + 1;j++) l[i][j] = 1e9; l[start][can + 1] = 0; priority_queue <doges> pq; pq.push({start,can + 1,l[start][can + 1]}); while (pq.size()) { int pos = pq.top().vertice,jump = pq.top().jump,cost = pq.top().cost; pq.pop(); if (cost > l[pos][jump]) continue; if (pos == end) { cout << l[pos][jump]; exit(0); } //TH1: Tiep tuc dung jump if (jump <= can) { if (pos - jump >= 1 && l[pos - jump][jump] > cost + 1) { l[pos - jump][jump] = cost + 1; pq.push({pos - jump,jump,l[pos - jump][jump]}); } if (pos + jump <= n && l[pos + jump][jump] > cost + 1) { l[pos + jump][jump] = cost + 1; pq.push({pos + jump,jump,l[pos + jump][jump]}); } } //TH2: Dung power khac for (auto pw : power[pos]) { if (pw > can) { for (int i = 1;pos - i * pw >= 1;i++) { if (l[pos - i * pw][can + 1] > cost + i) { l[pos - i * pw][can + 1] = cost + i; pq.push({pos - i * pw,can + 1,l[pos - i * pw][can + 1]}); } } for (int i = 1;pos + i * pw <= n;i++) { if (l[pos + i * pw][can + 1] > cost + i) { l[pos + i * pw][can + 1] = cost + i; pq.push({pos + i * pw,can + 1,l[pos + i * pw][can + 1]}); } } } else { if (l[pos][pw] > cost) { l[pos][pw] = cost; pq.push({pos,pw,l[pos][pw]}); } } } } cout << -1; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); // freopen(".inp","r",stdin); // freopen(".out","w",stdout); cin >> n >> m; for (int i = 1;i <= m;i++) { int b,p;cin >> b >> p; b++; if (i == 1) start = b; if (i == 2) end = b; power[b].push_back(p); } djt(); } /* Thuong em khi mua thu Thuong em sang mua ha Thuong em bang qua mua dong,gui gio xuan om em vao long Thuong em bao mua mua Tham thuong luon bao mua nang Thuong yeu em khong doi thay,gio mat em tim toi hao gay ): */
#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...