Submission #656858

#	Time	Username	Problem	Language	Result	Execution time	Memory
656858		Melika0gh	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	62 ms	3532 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

const int maxn = 102, maxk = 1e3+2, inf = 1e9+10;
ll b[maxn][maxk], s[maxn][maxk], max_ben[maxn][maxn], dis[maxn][maxn];
int N, M, K;

struct edge
{
	int v, u;
};

vector<edge> edges;

void FloydWarshall()
{
	for(int v = 0; v < N; v++)
		dis[v][v] = 0;
	
	for(int k = 0; k < N; k++)
	{
		for(int v = 0; v < N; v++)
		{
			for(int u = 0; u < N; u++)
			{
				dis[v][u] = min(dis[u][v], dis[v][k] + dis[k][u]);
			}
		}
	}
	
	return;
}

void CalcBen()
{
	for(int v = 0; v < N; v++)
	{
		for(int u = 0; u < N; u++)
		{
			max_ben[v][u] = 0;
			for(int k = 0; k < K; k++)
			{
				if(b[v][k] != -1 && s[u][k] != -1)
					max_ben[v][u] = max(max_ben[v][u], s[u][k] - b[v][k]);
			}
		}
	}
	
	return;
}

bool Valid(ll x)
{
	edges.clear();
	ll w[maxn][maxn], d[maxn];
	for(int v = 0; v < N; v++)
	{
		d[v] = inf;
		for(int u = 0; u < N; u++)
		{
			w[v][u] = x * dis[v][u] - max_ben[v][u];
			edges.push_back({v, u});
		}
	}
	d[0] = 0;
	
	for(int i = 0; i < N; i++)
	{
		for(auto tmp : edges)
		{
			int v = tmp.v, u = tmp.u;
			if(d[u] > d[v] + w[v][u])
			{
				d[u] = d[v] + w[v][u];
			}
		}
	}
	
	for(auto tmp : edges)
	{
		int v = tmp.v, u = tmp.u;
		if(d[u] > d[v] + w[v][u])
		{
			d[u] = d[v] + w[v][u];
			return true;
		}
	}
	
	return false;
}

int Bs(int l, int r)
{
	if(r - l <= 1)
	{
		return l;
	}
	
	int mid = (l + r) / 2;
	if(Valid(mid))
		return Bs(mid, r);
	else
		return Bs(l, mid);
}

int main()
{
	ios::sync_with_stdio(0),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];
	
	memset(dis, 63, sizeof dis);
	for(int i = 0; i < M; i++)
	{
		int v, u, w;
		cin >> v >> u >> w;
		v--, u--;
		dis[v][u] = w;
	}
	
	FloydWarshall();
	CalcBen();
	
	int ans = Bs(0, inf);
	cout << ans << '\n';
	
	return 0;
}

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