# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
258971 | Bruteforceman | Treatment Project (JOI20_treatment) | C++11 | 3074 ms | 4472 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const long long inf = 1e16;
long long d[maxn];
struct data {
int t, l, r, c;
} a[maxn];
int n;
int par[maxn];
int leftAfter(int x, int t) {
if(x == 1) return 1;
return x + t;
}
int rightAfter(int x, int t) {
if(x == n) return n;
return x - t;
}
bool isEdge(data p, data q) {
if(p.t <= q.t) {
return (q.l <= p.r - abs(q.t - p.t));
} else {
return (q.l + abs(p.t - q.t) <= p.r);
}
}
int main() {
int m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d %d %d %d", &a[i].t, &a[i].l, &a[i].r, &a[i].c);
a[i].l -= 1;
}
priority_queue <pair <long long, int>,
vector <pair <long long, int>>,
greater <pair <long long, int>>> Q;
for(int i = 1; i <= m; i++) {
if(a[i].l == 0) {
d[i] = a[i].c;
Q.emplace(d[i], i);
} else {
d[i] = inf;
}
}
while(!Q.empty()) {
int node = Q.top().second;
long long dist = Q.top().first;
Q.pop();
if(dist != d[node]) continue;
for(int i = 1; i <= m; i++) {
if(isEdge(a[node], a[i]) && par[i] == 0) {
d[i] = d[node] + a[i].c;
par[i] = node;
Q.emplace(d[i], i);
}
}
}
long long ans = inf;
for(int i = 1; i <= m; i++) {
if(a[i].r == n) ans = min(ans, d[i]);
}
if(ans == inf) ans = -1;
printf("%lld\n", ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |