Cod sursa(job #2513976)

Utilizator bluestorm57Vasile T bluestorm57 Data 24 decembrie 2019 11:59:48
Problema Amenzi Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("amenzi.in");
ofstream g("amenzi.out");

const int NMAX = 155;
const int TMAX = 3501;

int mat[NMAX][TMAX],n,m,K,p;
int dp[NMAX][TMAX];
vector < pair < int, int > > v[NMAX];

int main(){
    f >> n >> m >> K >> p;
    for(int i = 1 ; i <= m ; i++){
        int x,y,z;
        f >> x >> y >> z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    for(int i = 1 ; i <= K ; i++){
        int x,y,z;
        f >> x >> y >> z;
        mat[x][y] += z;
    }

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

    dp[1][0] = mat[1][0];
    for(int i = 1 ; i < TMAX ; i++)
        for(int j = 1 ; j <= n ; j++){

            dp[j][i] = dp[j][i - 1];

            for(auto it: v[j]){

                if(i >= it.second)
                    dp[j][i] = max(dp[j][i], dp[it.first][i - it.second]);

            }
            if(dp[j][i] != -1)
                dp[j][i] += mat[j][i];
        }

    while(p--){
        int x,y;
        f >> x >> y;
        g << dp[x][y] << "\n";
    }

    return 0;
}