#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Nmax=5010, INF=1e18;
int N, M, T[Nmax], L[Nmax], R[Nmax], C[Nmax], D[Nmax];
vector<int> adj[Nmax];
priority_queue<pair<int, int>> PQ;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>M;
for(int i=1; i<=M; i++) {
cin>>T[i]>>L[i]>>R[i]>>C[i];
if(L[i]==1) adj[0].push_back(i);
if(R[i]==N) adj[i].push_back(M+1);
}
for(int i=1; i<=M; i++) for(int j=i+1; j<=M; j++) {
int l1=L[i]+max(0ll, T[j]-T[i]), r1=R[i]-max(0ll, T[j]-T[i]);
if(L[i]==1) l1=1; if(R[i]==N) r1=N;
int l2=L[j]+max(0ll, T[i]-T[j]), r2=R[j]-max(0ll, T[i]-T[j]);
if(L[j]==1) l2=1; if(R[j]==N) r2=N;
if(l1>r1 || l2>r2) continue;
if(!(l1>r2+1 || l2>r1+1)) adj[i].push_back(j), adj[j].push_back(i);
}
fill(D+1, D+M+2, INF);
PQ.push({0, 0});
while(!PQ.empty()) {
int curr=PQ.top().second, dist=-PQ.top().first; PQ.pop();
if(dist!=D[curr]) continue;
for(int next:adj[curr]) if(D[next]>D[curr]+C[next]) D[next]=D[curr]+C[next], PQ.push({-D[next], next});
}
if(D[M+1]==INF) cout<<-1;
else cout<<D[M+1];
return 0;
}
Compilation message
treatment.cpp: In function 'int main()':
treatment.cpp:20:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
20 | if(L[i]==1) l1=1; if(R[i]==N) r1=N;
| ^~
treatment.cpp:20:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
20 | if(L[i]==1) l1=1; if(R[i]==N) r1=N;
| ^~
treatment.cpp:22:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if(L[j]==1) l2=1; if(R[j]==N) r2=N;
| ^~
treatment.cpp:22:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
22 | if(L[j]==1) l2=1; if(R[j]==N) r2=N;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
