//Jakarta skysrcapers
#include <bits/stdc++.h>
#define INF MOD
#define MOD 100000007
#define MAX_N 30005
#define MAX_M 30005
#define K 0.97
int mg;
using namespace std;
int N, M;
int source, dest;
struct edge{
int d, w;
};
vector<int> soli[MAX_N];
int dist[MAX_N];
bool mark[MAX_N];
clock_t t;
bool legal;
void dijkstra(int s){
if(clock()-t>K*CLOCKS_PER_SEC){legal=0;return;}
memset(dist, INF, sizeof(dist));
memset(mark, 0, sizeof(mark));
dist[s]=0;
priority_queue<pair<int, int> > pq;
pq.emplace(0, s);
while(!pq.empty()){
auto cur=pq.top();
pq.pop();
int v=cur.second;
if(mark[v])continue;
mark[v]=1;
if(v==dest)return;
int d=soli[v].size();
for(int j=0; j<d; ++j){
int p=soli[v][j];
int sk=v-p;
while(sk>=0 && sk>v-mg*p){
int w=(v-sk)/p;
if(!mark[sk] && dist[sk]>dist[v]+w && soli[sk].size()>0){
dist[sk]=dist[v]+w;
pq.emplace(-1*(dist[v]+w), sk);
}
sk-=p;
}
sk=v+p;
while(sk<N && sk<v+mg*p){
int w=(sk-v)/p;
if(!mark[sk] && dist[sk]>dist[v]+w && soli[sk].size()>0){
dist[sk]=dist[v]+w;
pq.emplace(-1*(dist[v]+w), sk);
}
sk+=p;
}
if(clock()-t>K*CLOCKS_PER_SEC){legal=0;return;}
}
}
}
inline bool cmp(int i, int j){return i>j;}
int main(){
ios::sync_with_stdio(false);
cin>>N>>M;
int b;
cin>>source>>b;
soli[source].push_back(b);
cin>>dest>>b;
soli[dest].push_back(b);
for(int i=2; i<M; ++i){
int p;
cin>>b>>p;
soli[b].push_back(p);
}
t=clock();
for(int i=0; i<N; ++i){
sort(soli[i].begin(), soli[i].end(), cmp);
}
mg=7000;
legal=1;
dijkstra(source);
int output=dist[dest]>100000000?-1:dist[dest];
mg=30000;
if(legal)
dijkstra(source);
if(!legal){cout<<output;return 0;}
if(dist[dest]>100000000)cout<<"-1"<<endl;
else
cout<<dist[dest];
return 0;
}
/*
5 3
0 2
1 1
4 1
*/
/*
4 4
0 1 1
1 2 2
2 3 1
1 3 4
0 3
5 6
0 1 1
1 2 2
2 3 1
1 3 4
0 4 2
4 3 1
0 3
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1152 KB |
Output is correct |
2 |
Correct |
2 ms |
1152 KB |
Output is correct |
3 |
Correct |
3 ms |
1152 KB |
Output is correct |
4 |
Correct |
3 ms |
1152 KB |
Output is correct |
5 |
Correct |
3 ms |
1152 KB |
Output is correct |
6 |
Correct |
3 ms |
1152 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1152 KB |
Output is correct |
2 |
Correct |
3 ms |
1152 KB |
Output is correct |
3 |
Correct |
4 ms |
1152 KB |
Output is correct |
4 |
Correct |
4 ms |
1152 KB |
Output is correct |
5 |
Correct |
3 ms |
1152 KB |
Output is correct |
6 |
Correct |
3 ms |
1152 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 |
1280 KB |
Output is correct |
11 |
Correct |
4 ms |
1152 KB |
Output is correct |
12 |
Correct |
4 ms |
1152 KB |
Output is correct |
13 |
Correct |
7 ms |
1152 KB |
Output is correct |
14 |
Correct |
7 ms |
1280 KB |
Output is correct |
15 |
Correct |
5 ms |
1152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1152 KB |
Output is correct |
2 |
Correct |
4 ms |
1152 KB |
Output is correct |
3 |
Correct |
3 ms |
1152 KB |
Output is correct |
4 |
Correct |
3 ms |
1152 KB |
Output is correct |
5 |
Correct |
2 ms |
1152 KB |
Output is correct |
6 |
Correct |
3 ms |
1152 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
8 |
Correct |
4 ms |
1152 KB |
Output is correct |
9 |
Correct |
3 ms |
1152 KB |
Output is correct |
10 |
Correct |
4 ms |
1280 KB |
Output is correct |
11 |
Correct |
4 ms |
1280 KB |
Output is correct |
12 |
Correct |
3 ms |
1280 KB |
Output is correct |
13 |
Correct |
6 ms |
1280 KB |
Output is correct |
14 |
Correct |
5 ms |
1280 KB |
Output is correct |
15 |
Correct |
5 ms |
1280 KB |
Output is correct |
16 |
Correct |
4 ms |
1280 KB |
Output is correct |
17 |
Correct |
7 ms |
1280 KB |
Output is correct |
18 |
Correct |
3 ms |
1280 KB |
Output is correct |
19 |
Correct |
4 ms |
1280 KB |
Output is correct |
20 |
Correct |
31 ms |
1280 KB |
Output is correct |
21 |
Correct |
3 ms |
1280 KB |
Output is correct |
22 |
Correct |
3 ms |
1280 KB |
Output is correct |
23 |
Correct |
12 ms |
1276 KB |
Output is correct |
24 |
Correct |
6 ms |
1280 KB |
Output is correct |
25 |
Correct |
4 ms |
1280 KB |
Output is correct |
26 |
Correct |
4 ms |
1152 KB |
Output is correct |
27 |
Correct |
4 ms |
1280 KB |
Output is correct |
28 |
Correct |
6 ms |
1280 KB |
Output is correct |
29 |
Correct |
5 ms |
1280 KB |
Output is correct |
30 |
Correct |
4 ms |
1280 KB |
Output is correct |
31 |
Correct |
4 ms |
1152 KB |
Output is correct |
32 |
Correct |
4 ms |
1280 KB |
Output is correct |
33 |
Correct |
7 ms |
1280 KB |
Output is correct |
34 |
Correct |
6 ms |
1152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1152 KB |
Output is correct |
2 |
Correct |
2 ms |
1152 KB |
Output is correct |
3 |
Correct |
4 ms |
1152 KB |
Output is correct |
4 |
Correct |
3 ms |
1152 KB |
Output is correct |
5 |
Correct |
3 ms |
1152 KB |
Output is correct |
6 |
Correct |
3 ms |
1152 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
8 |
Correct |
17 ms |
1152 KB |
Output is correct |
9 |
Correct |
4 ms |
1152 KB |
Output is correct |
10 |
Correct |
3 ms |
1152 KB |
Output is correct |
11 |
Correct |
4 ms |
1280 KB |
Output is correct |
12 |
Correct |
3 ms |
1280 KB |
Output is correct |
13 |
Correct |
5 ms |
1280 KB |
Output is correct |
14 |
Correct |
5 ms |
1280 KB |
Output is correct |
15 |
Correct |
5 ms |
1280 KB |
Output is correct |
16 |
Correct |
3 ms |
1280 KB |
Output is correct |
17 |
Correct |
5 ms |
1280 KB |
Output is correct |
18 |
Correct |
3 ms |
1152 KB |
Output is correct |
19 |
Correct |
3 ms |
1152 KB |
Output is correct |
20 |
Correct |
30 ms |
1280 KB |
Output is correct |
21 |
Correct |
3 ms |
1152 KB |
Output is correct |
22 |
Correct |
4 ms |
1280 KB |
Output is correct |
23 |
Correct |
5 ms |
1280 KB |
Output is correct |
24 |
Correct |
7 ms |
1280 KB |
Output is correct |
25 |
Correct |
4 ms |
1280 KB |
Output is correct |
26 |
Correct |
4 ms |
1280 KB |
Output is correct |
27 |
Correct |
5 ms |
1152 KB |
Output is correct |
28 |
Correct |
9 ms |
1280 KB |
Output is correct |
29 |
Correct |
6 ms |
1280 KB |
Output is correct |
30 |
Correct |
5 ms |
1152 KB |
Output is correct |
31 |
Correct |
5 ms |
1280 KB |
Output is correct |
32 |
Correct |
4 ms |
1280 KB |
Output is correct |
33 |
Correct |
8 ms |
1280 KB |
Output is correct |
34 |
Correct |
8 ms |
1152 KB |
Output is correct |
35 |
Correct |
35 ms |
1536 KB |
Output is correct |
36 |
Correct |
5 ms |
1280 KB |
Output is correct |
37 |
Correct |
16 ms |
1536 KB |
Output is correct |
38 |
Correct |
41 ms |
1536 KB |
Output is correct |
39 |
Correct |
10 ms |
1408 KB |
Output is correct |
40 |
Correct |
14 ms |
1536 KB |
Output is correct |
41 |
Correct |
40 ms |
1612 KB |
Output is correct |
42 |
Correct |
9 ms |
1408 KB |
Output is correct |
43 |
Correct |
9 ms |
1408 KB |
Output is correct |
44 |
Correct |
232 ms |
1408 KB |
Output is correct |
45 |
Correct |
45 ms |
1408 KB |
Output is correct |
46 |
Correct |
45 ms |
1408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1152 KB |
Output is correct |
2 |
Correct |
3 ms |
1152 KB |
Output is correct |
3 |
Correct |
3 ms |
1408 KB |
Output is correct |
4 |
Correct |
4 ms |
1280 KB |
Output is correct |
5 |
Correct |
2 ms |
1024 KB |
Output is correct |
6 |
Correct |
3 ms |
1152 KB |
Output is correct |
7 |
Correct |
3 ms |
1152 KB |
Output is correct |
8 |
Correct |
2 ms |
1152 KB |
Output is correct |
9 |
Correct |
2 ms |
1152 KB |
Output is correct |
10 |
Correct |
3 ms |
1280 KB |
Output is correct |
11 |
Correct |
4 ms |
1280 KB |
Output is correct |
12 |
Correct |
3 ms |
1280 KB |
Output is correct |
13 |
Correct |
5 ms |
1280 KB |
Output is correct |
14 |
Correct |
6 ms |
1152 KB |
Output is correct |
15 |
Correct |
7 ms |
1152 KB |
Output is correct |
16 |
Correct |
2 ms |
1152 KB |
Output is correct |
17 |
Correct |
5 ms |
1324 KB |
Output is correct |
18 |
Correct |
3 ms |
1280 KB |
Output is correct |
19 |
Correct |
4 ms |
1280 KB |
Output is correct |
20 |
Correct |
33 ms |
1280 KB |
Output is correct |
21 |
Correct |
3 ms |
1152 KB |
Output is correct |
22 |
Correct |
3 ms |
1280 KB |
Output is correct |
23 |
Correct |
5 ms |
1152 KB |
Output is correct |
24 |
Correct |
8 ms |
1408 KB |
Output is correct |
25 |
Correct |
5 ms |
1280 KB |
Output is correct |
26 |
Correct |
4 ms |
1280 KB |
Output is correct |
27 |
Correct |
4 ms |
1152 KB |
Output is correct |
28 |
Correct |
7 ms |
1280 KB |
Output is correct |
29 |
Correct |
5 ms |
1152 KB |
Output is correct |
30 |
Correct |
3 ms |
1152 KB |
Output is correct |
31 |
Correct |
4 ms |
1152 KB |
Output is correct |
32 |
Correct |
7 ms |
1152 KB |
Output is correct |
33 |
Correct |
6 ms |
1256 KB |
Output is correct |
34 |
Correct |
10 ms |
1280 KB |
Output is correct |
35 |
Correct |
35 ms |
1536 KB |
Output is correct |
36 |
Correct |
6 ms |
1280 KB |
Output is correct |
37 |
Correct |
16 ms |
1536 KB |
Output is correct |
38 |
Correct |
44 ms |
1536 KB |
Output is correct |
39 |
Correct |
11 ms |
1408 KB |
Output is correct |
40 |
Correct |
15 ms |
1536 KB |
Output is correct |
41 |
Correct |
42 ms |
1536 KB |
Output is correct |
42 |
Correct |
12 ms |
1452 KB |
Output is correct |
43 |
Correct |
14 ms |
1536 KB |
Output is correct |
44 |
Correct |
211 ms |
1528 KB |
Output is correct |
45 |
Correct |
44 ms |
1408 KB |
Output is correct |
46 |
Correct |
44 ms |
1408 KB |
Output is correct |
47 |
Correct |
26 ms |
2280 KB |
Output is correct |
48 |
Correct |
12 ms |
1664 KB |
Output is correct |
49 |
Correct |
10 ms |
1664 KB |
Output is correct |
50 |
Correct |
7 ms |
1536 KB |
Output is correct |
51 |
Correct |
56 ms |
2560 KB |
Output is correct |
52 |
Correct |
60 ms |
2548 KB |
Output is correct |
53 |
Correct |
20 ms |
2048 KB |
Output is correct |
54 |
Correct |
3 ms |
1152 KB |
Output is correct |
55 |
Correct |
3 ms |
1152 KB |
Output is correct |
56 |
Incorrect |
982 ms |
2296 KB |
Output isn't correct |
57 |
Halted |
0 ms |
0 KB |
- |