#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 5e3 + 5, M = 3e6 + 5;
const ll oo = 1e18 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7, mod2 = 1e9+3;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define NAME code
using namespace std;
int n, m;
struct node{
int t, l, r, c;
}a[nmax];
ll dp[nmax];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= m; ++i) cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
for(int i = 1; i <= m; ++i) dp[i] = oo;
priority_queue<pii, vector<pii>, greater<pii>> q;
for(int i = 1; i <= m; ++i){
if(a[i].l == 1){
dp[i] = a[i].c;
q.push({dp[i], i});
}
}
while(q.size()){
pii tmp = q.top();q.pop();
int u = tmp.se;
for(int i = 1; i <= m; ++i){
if(a[u].r - a[i].l + 1 >= abs(a[u].t - a[i].t)){
if(dp[i] > dp[u] + a[i].c){
dp[i] = dp[u] + a[i].c;
q.push({dp[i], i});
}
}
}
}
ll ans = oo;
for(int i = 1; i <= m; ++i) if(a[i].r == n) ans = min(ans, dp[i]);
if(ans == oo) cout << -1;
else cout << ans;
}
/*
10 5
1 1 3 1
1 1 6 5
1 4 8 3
1 5 10 4
1 6 10 3
*/
Compilation message
treatment.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
21 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
348 KB |
Output is correct |
| 16 |
Correct |
0 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
44 ms |
604 KB |
Output is correct |
| 21 |
Correct |
44 ms |
860 KB |
Output is correct |
| 22 |
Correct |
33 ms |
600 KB |
Output is correct |
| 23 |
Correct |
21 ms |
816 KB |
Output is correct |
| 24 |
Correct |
61 ms |
956 KB |
Output is correct |
| 25 |
Correct |
37 ms |
604 KB |
Output is correct |
| 26 |
Correct |
32 ms |
604 KB |
Output is correct |
| 27 |
Correct |
31 ms |
852 KB |
Output is correct |
| 28 |
Correct |
55 ms |
860 KB |
Output is correct |
| 29 |
Correct |
32 ms |
604 KB |
Output is correct |
| 30 |
Correct |
2 ms |
604 KB |
Output is correct |
| 31 |
Correct |
2 ms |
848 KB |
Output is correct |
| 32 |
Correct |
103 ms |
860 KB |
Output is correct |
| 33 |
Correct |
60 ms |
860 KB |
Output is correct |
| 34 |
Correct |
40 ms |
604 KB |
Output is correct |
| 35 |
Correct |
103 ms |
856 KB |
Output is correct |
| 36 |
Correct |
56 ms |
860 KB |
Output is correct |
| 37 |
Correct |
38 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
