#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 30007, INF = (1e9) + 7;
struct el {
int to, cost;
el() {}
el(int a, int b): to(a), cost(b) {}
bool operator <(const el &a) const {
return cost > a.cost;
}
};
int n, m, start[N], jump[N], dist[N];
vector < int > v[N];
bool in[N];
void spfa() {
queue < int > q;
int i, j, curr, current_distance;
fill(dist, dist + n, INF);
dist[start[0]] = 0;
q.push(start[0]);
in[start[0]] = true;
while(!q.empty() && clock()<=0.90*CLOCKS_PER_SEC) {
curr = q.front();
q.pop();
in[curr] = false;
for(i=0;i<(int)(v[curr].size()) && clock()<=0.90*CLOCKS_PER_SEC;i++) {
for(j=1;curr+j*v[curr][i]<n;j++) {
current_distance = dist[curr] + j;
if(current_distance<dist[curr + j*v[curr][i]]) {
dist[curr + j*v[curr][i]] = current_distance;
if(!in[curr + j*v[curr][i]]) {
q.push(curr + j*v[curr][i]);
in[curr + j*v[curr][i]] = true;
}
}
}
for(j=-1;curr+j*v[curr][i]>=0;j--) {
current_distance = dist[curr] - j;
if(current_distance<dist[curr + j*v[curr][i]]) {
dist[curr + j*v[curr][i]] = current_distance;
if(!in[curr + j*v[curr][i]]) {
q.push(curr + j*v[curr][i]);
in[curr + j*v[curr][i]] = true;
}
}
}
}
}
}
void dijkstra() {
priority_queue < el > q;
el curr;
int i, j, current_distance;
fill(dist, dist + n, INF);
dist[start[0]] = 0;
q.push(el(start[0], 0));
while(!q.empty()) {
curr = q.top();
q.pop();
if(curr.cost!=dist[curr.to]) continue;
for(i=0;i<(int)(v[curr.to].size());i++) {
for(j=1;curr.to+j*v[curr.to][i]<n;j++) {
current_distance = curr.cost + j;
if(current_distance<dist[curr.to+j*v[curr.to][i]]) {
dist[curr.to+j*v[curr.to][i]] = current_distance;
q.push(el(curr.to+j*v[curr.to][i], current_distance));
}
}
for(j=-1;curr.to+j*v[curr.to][i]>=0;j--) {
current_distance = curr.cost - j;
if(current_distance<dist[curr.to+j*v[curr.to][i]]) {
dist[curr.to+j*v[curr.to][i]] = current_distance;
q.push(el(curr.to+j*v[curr.to][i], current_distance));
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i;
scanf("%d %d", &n, &m);
for(i=0;i<m;i++) {
scanf("%d %d", &start[i], &jump[i]);
v[start[i]].push_back(jump[i]);
}
spfa();
printf("%d\n", dist[start[1]]==INF ? -1 : dist[start[1]]);
return 0;
}
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &start[i], &jump[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1072 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1024 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1152 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1148 KB |
Output is correct |
| 15 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 19 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 20 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 23 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 24 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 25 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 27 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 28 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 29 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 30 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 31 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 32 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 33 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 34 |
Correct |
6 ms |
1152 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 11 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 13 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 16 |
Correct |
2 ms |
1020 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1212 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 23 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 24 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 25 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 26 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 27 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 28 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 29 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 30 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 31 |
Correct |
5 ms |
1024 KB |
Output is correct |
| 32 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 33 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 34 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 35 |
Correct |
35 ms |
1536 KB |
Output is correct |
| 36 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 37 |
Correct |
24 ms |
1408 KB |
Output is correct |
| 38 |
Correct |
33 ms |
1536 KB |
Output is correct |
| 39 |
Correct |
32 ms |
1536 KB |
Output is correct |
| 40 |
Correct |
39 ms |
1536 KB |
Output is correct |
| 41 |
Correct |
39 ms |
1536 KB |
Output is correct |
| 42 |
Correct |
99 ms |
1588 KB |
Output is correct |
| 43 |
Correct |
95 ms |
1536 KB |
Output is correct |
| 44 |
Correct |
101 ms |
1536 KB |
Output is correct |
| 45 |
Correct |
27 ms |
1408 KB |
Output is correct |
| 46 |
Correct |
28 ms |
1408 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1152 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1124 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 17 |
Correct |
5 ms |
1152 KB |
Output is correct |
| 18 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 20 |
Correct |
11 ms |
1152 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1152 KB |
Output is correct |
| 23 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 24 |
Correct |
8 ms |
1152 KB |
Output is correct |
| 25 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 26 |
Correct |
10 ms |
1152 KB |
Output is correct |
| 27 |
Correct |
14 ms |
1152 KB |
Output is correct |
| 28 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 29 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 30 |
Correct |
4 ms |
1152 KB |
Output is correct |
| 31 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 32 |
Correct |
4 ms |
1024 KB |
Output is correct |
| 33 |
Correct |
7 ms |
1152 KB |
Output is correct |
| 34 |
Correct |
6 ms |
1152 KB |
Output is correct |
| 35 |
Correct |
24 ms |
1536 KB |
Output is correct |
| 36 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 37 |
Correct |
24 ms |
1380 KB |
Output is correct |
| 38 |
Correct |
31 ms |
1664 KB |
Output is correct |
| 39 |
Correct |
30 ms |
1536 KB |
Output is correct |
| 40 |
Correct |
39 ms |
1536 KB |
Output is correct |
| 41 |
Correct |
38 ms |
1656 KB |
Output is correct |
| 42 |
Correct |
91 ms |
1536 KB |
Output is correct |
| 43 |
Correct |
92 ms |
1624 KB |
Output is correct |
| 44 |
Correct |
102 ms |
1612 KB |
Output is correct |
| 45 |
Correct |
28 ms |
1536 KB |
Output is correct |
| 46 |
Correct |
28 ms |
1536 KB |
Output is correct |
| 47 |
Correct |
54 ms |
1664 KB |
Output is correct |
| 48 |
Correct |
10 ms |
1792 KB |
Output is correct |
| 49 |
Correct |
11 ms |
1820 KB |
Output is correct |
| 50 |
Correct |
10 ms |
1664 KB |
Output is correct |
| 51 |
Correct |
136 ms |
2176 KB |
Output is correct |
| 52 |
Correct |
211 ms |
2176 KB |
Output is correct |
| 53 |
Correct |
75 ms |
2048 KB |
Output is correct |
| 54 |
Correct |
12 ms |
1280 KB |
Output is correct |
| 55 |
Correct |
14 ms |
1280 KB |
Output is correct |
| 56 |
Correct |
902 ms |
2560 KB |
Output is correct |
| 57 |
Correct |
87 ms |
1408 KB |
Output is correct |
| 58 |
Correct |
900 ms |
1756 KB |
Output is correct |
| 59 |
Correct |
900 ms |
2040 KB |
Output is correct |
| 60 |
Correct |
900 ms |
2116 KB |
Output is correct |
| 61 |
Correct |
900 ms |
2116 KB |
Output is correct |
| 62 |
Correct |
52 ms |
2808 KB |
Output is correct |
| 63 |
Correct |
46 ms |
1920 KB |
Output is correct |
| 64 |
Correct |
46 ms |
1996 KB |
Output is correct |
| 65 |
Correct |
55 ms |
2044 KB |
Output is correct |
| 66 |
Correct |
53 ms |
1988 KB |
Output is correct |
| 67 |
Correct |
55 ms |
1952 KB |
Output is correct |
