Cod sursa(job #2009923)

Utilizator andru47Stefanescu Andru andru47 Data 11 august 2017 11:53:21
Problema Amenzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>
#define f first
#define s second
#define inf -8372918
using namespace std;
int n,m,k,p,dp[3505][155],tickets[3505][155];
vector < pair<int , int> > g[155];
int main() {
    freopen("amenzi.in" , "r", stdin);
    freopen("amenzi.out" , "w", stdout);

    scanf("%d %d %d %d\n", &n, &m, &k, &p);
    for (int i = 1; i<=m; ++i) {
        int x , y , t;
        scanf("%d %d %d\n", &x, &y, &t);
        g[x].push_back({y , t});
        g[y].push_back({x , t});
    }
    for (int i = 1; i<=k; ++i) {
        int x , y , t;
        scanf("%d %d %d\n", &x, &y, &t);
        tickets[y][x] += t;
    }
    for (int i = 0; i<=3500; ++i)
        for (int j = 1; j<=n; ++j)
            dp[i][j] = inf;
    dp[0][1] = tickets[0][1];
    for (int i = 1; i<=3500; ++i)
        for (int j = 1; j<=n; ++j) {
            for (auto &it : g[j])
                if (i >= it.s)
                    dp[i][j] = max(dp[i][j] , dp[i - it.s][it.f]);
            dp[i][j] = max(dp[i][j] , dp[i - 1][j]);
            if (dp[i][j] != inf)
                dp[i][j] += tickets[i][j];
        }
    for (int i = 1; i<=p; ++i) {
        int x , y;
        scanf("%d %d\n", &x, &y);
        printf("%d\n", dp[y][x]);
    }
    return 0;
}