#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;
assert(M<=5000);
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]);
int l2=L[j]+max(0ll, T[i]-T[j]), r2=R[j]-max(0ll, T[i]-T[j]);
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |