#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int INF=1e17;
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
vector<int> a(m), b(m), dist(m);
vector<vector<pii>> adj(m);
for(int i=0; i<m; i++) cin >> a[i] >> b[i], dist[i]=INF;
for(int i=0; i<m; i++) {
for(int j=0; j<m; j++) {
if(i==j) continue;
if(abs(a[i]-a[j])%b[i]) continue;
adj[i].push_back({j, abs(a[i]-a[j])/b[i]});
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, 0});
dist[0]=0; vector<bool> vis(m);
while(!pq.empty()) {
int cur=pq.top().first, u=pq.top().second;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto p : adj[u]) {
if(dist[p.first]>dist[u]+p.second) {
dist[p.first]=dist[u]+p.second;
pq.push({dist[p.first], p.first});
}
}
}
cout << dist[1] << '\n';
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:9: warning: unused variable 'cur' [-Wunused-variable]
23 | int cur=pq.top().first, u=pq.top().second;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |