Submission #372627

#	Time	Username	Problem	Language	Result	Execution time	Memory
372627		hivakarami	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	80 ms	4588 KiB

merchant

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
 
const int N = 100 + 100;
const int K = 1000 + 100;
const ll mod = 998244353;
const ll inf = 1e9 + 100;

int n, m, k;
ll dis[N][N], Dis[N][N], prf[N][N], s[N][K], b[N][K];



inline bool check(ll mid)
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{	
			if(dis[i][j] == inf)
				Dis[i][j] = -inf;
			else
				Dis[i][j] = prf[i][j] - dis[i][j] * mid;
		}
		Dis[i][i] = -inf;
	}
	
	/*
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cout << i+1 << ' ' << j+1 << ' ' << Dis[i][j] << endl;
		}
	}
	*/
	
	for(int t = 0; t < n; t++)
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				Dis[i][j] = max(Dis[i][j], Dis[i][t] + Dis[t][j]);
			}
		}
	}
	
	
	
	
	
	
	for(int i = 0; i < n; i++)
	{
		if(Dis[i][i] >= 0)
			return 1;
	}
	
	return 0;

} 


inline void floyd()
{

	for(int t = 0; t < n; t++)
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				dis[i][j] = min(dis[i][j], dis[i][t] + dis[t][j]);
			}
		}
	}

}



inline ll max_profit(int u, int v)
{
	ll ans = 0;
	for(int i = 0; i < k; i++)	
	{	
		if(s[v][i] != -1 && b[u][i] != -1)
			ans = max(ans, s[v][i] - b[u][i]);
	}
	
	return ans;
}



int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	
	
	
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < k; j++)
		{
			cin >> b[i][j] >> s[i][j];
		}
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			dis[i][j] = inf;
			prf[i][j] = max_profit(i, j);
		}
		dis[i][i] = 0;	
	}
	
	
	for(int i = 0; i < m; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		x--; y--;
		dis[x][y] = w;
	}
	
	
	floyd();
	
	
	
	/*
	cout << "//////////////////////////////////" << endl;

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			cout << i+1 << ' ' << j+1 << ' ' << dis[i][j] << ' ' << prf[i][j] << endl;
		}
	}

	cout << "//////////////////////////////////" << endl;
	*/


	ll l = 0, r = inf;
	
	while(l + 1 < r)
	{
		ll mid = (l + r) / 2;
		
		if(check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
		
	}
	
	cout << l << endl;
	
	
		
		
	return 0;
}




/*/
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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