Submission #853949

#	Time	Username	Problem	Language	Result	Execution time	Memory
853949		parsadox2	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	61 ms	4556 KiB

merchant

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define debug(x) cout << #x << " = " << x << " ";
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define S second
#define F first
#define int long long
using namespace std;
 
const int maxn = 1e2 + 10 , maxk = 1e3 + 10 , ili = 1e9 + 10;
const int inf = 1e18 + 10;
int n , m , k , s[maxn][maxk] , b[maxn][maxk] , c[maxn][maxn];
ll dis[maxn][maxn] , ans[maxn][maxn];
vector <pair<ll, int>> g[maxn];
 
void allinf(ll tmp[][maxn])
{
	for(int i = 0 ; i < maxn ; i++)
		for(int j = 0 ; j < maxn ; j++)
			tmp[i][j] = inf;
}
 
void floyd(ll dist[][maxn])
{
	for(int i = 0 ; i < n ; i++)
		for(auto u : g[i])
			dist[i][u.S] = min(dist[i][u.S] , u.F);
	for(int kk = 0 ; kk < n ; kk++)
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				dist[i][j] = min(dist[i][j] , dist[i][kk] + dist[kk][j]);
}
 
int C(int v , int u)
{
	int res = 0;
	for(int i = 0 ; i < k ; i++)
		if(b[v][i] != -1 && s[u][i] != -1)
			res = max(res , s[u][i] - b[v][i]);
	return res;
}
 
int32_t main()
{
	fast;
	
	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 < m ; i++)
	{
		int v , u , w;
		cin >> v >> u >> w;
		v--; u--;
		g[v].pb({w , u});
	}
	allinf(dis);
	floyd(dis);
	ll low = 0 , high = ili;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < n ; j++)
			if(i != j)
				c[i][j] = C(i , j);
	while(high - low > 1)
	{
		ll mid = (high + low) / 2;
		for(int i = 0 ; i < n ; i++)	g[i].clear();
		for(int i = 0 ; i < n ; i++)
			for(int j = 0 ; j < n ; j++)
				if(i != j)
					g[i].pb({(inf / dis[i][j] < mid ? inf : 1LL * mid * dis[i][j] - c[i][j]) , j});
		allinf(ans);
		floyd(ans);
		ll mn = 667;
		for(int i = 0 ; i < n ; i++) mn = min(mn , ans[i][i]);
		if(mn < 1)
			low = mid;
		else
			high = mid;
	}
	cout << low << endl;
	return 0;
}

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