Submission #561678

#	Time	Username	Problem	Language	Result	Execution time	Memory
561678		Garguy22	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	150 ms	4204 KiB

merchant

#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 107;
const ll INF = 1e18 + 7;

int n, m, kk;
ll b[MAXN][1007], s[MAXN][1007];
ll graph[MAXN][MAXN], adj[MAXN][MAXN], profit[MAXN][MAXN];

void shortest_path(ll dis[MAXN][MAXN]){
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= n; k++)
				dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
		}
	}
}

int main(){
	cin >> n >> m >> kk;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= kk; j++)
			cin >> b[i][j] >> s[i][j];
	}
	for(int i = 1; i <= n; i++){
	    for(int j = 1; j <= n; j++)
	        graph[i][j] = INF;
	}
	for(int i = 1; i <= m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		graph[x][y] = z;
	}
	shortest_path(graph);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= kk; k++){
				if(s[j][k] != -1 && b[i][k] != -1){
					profit[i][j] = max(profit[i][j], s[j][k] - b[i][k]);
				}
			}
		}
	}
	ll lef = 1, rig = 1e9;
	while(lef <= rig){
		ll mid = (lef + rig)/2;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				adj[i][j] = mid*min(graph[i][j], INF/mid) - profit[i][j];
		}
		shortest_path(adj);
		bool check = 0;
		for(int i = 1; i <= n; i++){
			if(adj[i][i] <= 0)
				check = 1;
		}
		if(check) 
			lef = mid + 1;
		else
			rig = mid - 1;
	}
	cout << rig << endl;

	return 0;	
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34