Cod sursa(job #2972470)

Utilizator DonchoBonbonchoAndon Tepavicharov DonchoBonboncho Data 29 ianuarie 2023 15:55:02
Problema Amenzi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 152;
const int MAX_T = 3500;
const int INF = 1e9;
const int mod = 1e9 + 7;

std::vector<std::pair<int, int>> v[MAX_N];

ll crimes[MAX_T + 42][MAX_N];

bool viz[MAX_T + 42][MAX_N];
ll dp[MAX_T + 42][MAX_N];

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	freopen( "fines.in", "r", stdin );
	freopen( "fines.out", "w", stdout );

	int n, m, k, p;
	std::cin>>n>>m>>k>>p;

	for( int i=0 ; i<m ; i++ ){
		int a, b, c;
		std::cin>>a>>b>>c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
	}

	for( int i=0 ; i<k ; i++ ){
		int a, b, c;
		std::cin>>a>>b>>c;
		crimes[b][a] += c;
	}

	viz[0][1] = true;

	for( int i=0 ; i <= MAX_T ; i++ ){
		for( int j=1 ; j<=n ; j++ ){
			for( auto cur : v[j] ){
				int curr = cur.first;
				int time = cur.second;

				if( i - time <  0 || !viz[i-time][curr] ) continue;
				viz[i][j] = true;
				
				dp[i][j] = std::max( dp[i][j], dp[i-time][curr] );

			}

			if( i > 0 ) viz[i][j] |= viz[i-1][j];
			if( viz[i][j] and i>0 ) dp[i][j] =std::max( dp[i][j], dp[i-1][j] + crimes[i][j]);

		}
	}

	while( p-- ){
		int a, b;
		std::cin>>a>>b;
		ll nas = -1;
		if( viz[b][a] ) nas = dp[b][a];

		std::cout<<nas<<"\n";
	}

	return 0;
}