CompetitiveProgramming/sharingchocolates.cpp at main · darksidergod/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

#define vi vector<int>
#define pb push_back
#define SIZE 6001
vi adj[SIZE];

int cost[SIZE][SIZE];
int points[SIZE];
int science[SIZE];


void dfs(int v, int capacity, int res)
{
	//cout<<"capacity at "<<v<<" is "<<capacity<<"\n";
	if(capacity<0)
		return;
	points[v]=res;
	for(int i=0; i<(int)adj[v].size(); i++)
	{
		int to=adj[v][i];
		//if(points[to]==0 || res+science[to]>points[to])
			dfs(to, capacity-cost[v][to], res+science[to]);
	}
}

int main(void)
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(cost, 0, sizeof(cost));
		memset(science, 0, sizeof(science));
		memset(points, 0, sizeof(points));
		int n, m, fuel;
		cin>>n>>m>>fuel;
		for(int i=0; i<n; i++)
			adj[i].clear();


		for(int i=0; i<n; i++)
			cin>>science[i];

		for(int i=0; i<m; i++)
		{
			int u, v, c;
			cin>>u>>v>>c;
			adj[u].pb(v);
			cost[u][v]=c;
		}

		dfs(0, fuel, science[0]);

		sort(points, points+n);
		cout<<points[n-1]<<"\n";a

	}
	return 0;
}