Cod sursa(job #2986048)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 27 februarie 2023 17:08:39
Problema Amenzi Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 150,
          MMAX = 1500,
          KMAX = 12000,
          PMAX = 8000,
          TMAX = 3500;

int n, m, k, p, dp[NMAX + 1][TMAX + 1], amenda[NMAX + 1][TMAX + 1];
vector<pair<int, int> > adj[NMAX + 1];

int main()
{
    freopen("amenzi.in", "r", stdin);
    freopen("amenzi.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &k, &p);
    for(int i = 1, x, y, c; i <= m; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    for(int i = 1, x, y, c; i <= k; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        amenda[x][y] = c;
    }

    for(int i = 1; i <= NMAX; ++i)
        for(int t = 0; t <= TMAX; ++t)
            dp[i][t] = -1;
    dp[1][0] = 0;

    for(int t = 1; t <= TMAX; ++t) {
        for(int i = 1; i <= n; ++i) {
            int crtamenda = amenda[i][t];
            if(dp[i][t - 1] >= 0)
                dp[i][t] = dp[i][t - 1] + crtamenda;
            for(const auto &el : adj[i]) {
                if(el.second <= t && dp[el.first][t - el.second] >= 0)
                    dp[i][t] = max(dp[i][t], dp[el.first][t - el.second] + crtamenda);
            }
        }
    }

//    for(int t = 0; t <= 10; ++t) cout << t << "\t"; cout << "\n";
//    for(int i = 1; i <= n; ++i, cout << "\n")
//        for(int t = 0; t <= 10; ++t)
//            cout << dp[i][t] << "\t";
//    cout << "\n";
//
//    for(int t = 11; t <= 20; ++t) cout << t << "\t"; cout << "\n";
//    for(int i = 1; i <= n; ++i, cout << "\n")
//        for(int t = 11; t <= 20; ++t)
//            cout << dp[i][t] << "\t";
//    cout << "\n";

    for(int i = 1, x, y; i <= p; ++i) {
        scanf("%d%d", &x, &y);
        printf("%d\n", dp[x][y]);
    }
    return 0;
}