#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
vector<tuple<int,int,int,int,int>> A;
vector<int> adj[5000];
int chk[5000];
long long dist[5000];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M;
priority_queue<pair<long long,int>> Q;
long long ans;
cin>>N>>M; A.resize(M);
memset(dist,0x3f,sizeof(dist));
for(int i=0;i<M;i++) {
auto &[t,l,r,aa,c]=A[i];
cin>>t>>l>>r>>c;
if(l--==1) chk[i]|=1;
if(r==N) chk[i]|=2;
tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
for(int j=0;j<i;j++) {
auto[x1,y1,x2,y2,t]=A[j];
if(max(x1,t)<=min(x2,r) && max(y1,l)<=min(y2,aa)) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
for(int i=0;i<M;i++) if(chk[i]&1) Q.emplace(-(dist[i]=get<4>(A[i])),i);
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
if(-t!=dist[c]) continue;
for(auto n: adj[c]) if(dist[n]==INF && dist[n]>dist[c]+get<4>(A[n])) {
dist[n]=dist[c]+get<4>(A[n]);
Q.emplace(-dist[n],n);
}
}
ans=INF;
for(int i=0;i<M;i++) if(chk[i]&2) ans=min(ans,dist[i]);
cout<<(ans<INF ? ans:-1)<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3036 ms |
2380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3036 ms |
2380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
