Submission #1169874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169874		Sharky	Treatment Project (JOI20_treatment)	C++20	35 / 100	342 ms	355172 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

#define L(i, j, k) for (int i = (j); i <= (k); i++)
#define R(i, j, k) for (int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()

const int N = 5005;
const int inf = 1e18;

struct Treatment {
    int t, l, r, c;
} arr[N];

int di[N];
vector<pair<int, int>> adj[2 * N];

void ae(int u, int v, int w) {
    // cout << "addedge: " << u << " " << v << " " << w << '\n';
    adj[u].push_back({v, w});
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> arr[i].t >> arr[i].l >> arr[i].r >> arr[i].c;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == j) continue;
            int td = abs(arr[i].t - arr[j].t);
            if (arr[j].l <= arr[i].r + 1 - td) ae(i, j, arr[j].c);
        }
        if (arr[i].l == 1) ae(0, i, arr[i].c);
    }
    di[0] = 0;
    for (int i = 1; i <= m; i++) di[i] = inf;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    q.push({0, 0});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d != di[u]) continue;
        for (auto& [v, w] : adj[u]) {
            if (di[v] > di[u] + w) {
                di[v] = di[u] + w;
                q.push({di[v], v});
            }
        }
    }
    int ans = inf;
    for (int i = 1; i <= m; i++) if (arr[i].r == n) ans = min(ans, di[i]);
    if (ans == inf) cout << "-1\n";
    else cout << ans << '\n';
    // sort projects, then point to interval edges
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

// [1, 5] 10
// [5. 11] 9
// ae(5, 12)
// ae(1, 6)

// [1, 5] 9
// [5, 11] 10
// ae(1, 6)
// ae(5, 12)

// [1, 5] 9
// [5, 11] 11
// ae(1, 6)
// ae(5, 12)


// extreme:

// [1, 6] 9
// [5, 11] 11

// [1, 5] 9
// [4, 11] 11
// ae(1, 6)
// ae(4, 12)

// time_distance = +2

// guy from rb of earlier thing MUST go left twice to visit the lb of the later thing!

// [1, 5] 10
// [5, 11] 9
// ae(1, 6)
// ae(5, 12)

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61