#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tii = array<int, 3>;
using pil = pair<int, ll>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()
const ll INF = 1e18;
int N, M;
map<int, vector<pair<pii, int>>> MP;
using abc = pair<ll, tii>;
abc in[100005];
priority_queue<abc, vector<abc>, greater<abc>> pq;
map<tii, ll> dist;
bool chk(tii a, tii b) {
if (a[0] > b[0]) swap(a, b);
return a[1] - a[0] - 1 <= b[1] - b[0] && b[1] + b[0] <= a[2] + a[0] + 1 ||
a[1] - a[0] - 1 <= b[2] - b[0] && b[2] + b[0] <= a[2] + a[0] + 1;
}
tii f(tii a, tii b) {
if (a[0] > b[0]) swap(a, b);
if (a[1] > 1) a[1] += b[0] - a[0];
if (a[2] < N) a[2] -= b[0] - a[0];
return {b[0], min(a[1], b[1]), max(a[2], b[2])};
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
int t, l, r, c; cin >> t >> l >> r >> c;
in[i] = {c, {t, l, r}};
if (l == 1) {
pq.push(in[i]);
tii n = {t, l, r};
if (!dist.count(n)) dist[n] = c;
else dist[n] = min(dist[n], (ll)c);
}
}
while (pq.size()) {
auto x = pq.top(); pq.pop();
ll c = x.ff;
int t = x.ss[0], l = x.ss[1], r = x.ss[2];
tii v = {t, l, r};
if (r == N) return !printf("%lld", c);
if (c > dist[v]) continue;
for (int i = 1; i <= M; ++i) if (chk(v, in[i].ss)) {
tii n = f(v, in[i].ss);
if (n == v) continue;
if (!dist.count(n) || dist[n] > c + in[i].ff) {
dist[n] = c + in[i].ff;
pq.emplace(c + in[i].ff, n);
}
}
}
cout << -1;
return 0;
}
Compilation message
treatment.cpp: In function 'bool chk(tii, tii)':
treatment.cpp:23:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
return a[1] - a[0] - 1 <= b[1] - b[0] && b[1] + b[0] <= a[2] + a[0] + 1 ||
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
3212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
3212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
