Submission #383329

#	Time	Username	Problem	Language	Result	Execution time	Memory
383329		Saynaa	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	163 ms	748 KiB

merchant

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 100 + 10;
const ll MAX = 1e17;
int n, m, k;
ll mat[MAXN][MAXN], tmp[MAXN][MAXN], b[MAXN][MAXN], s[MAXN][MAXN], res[MAXN][MAXN];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i ++){
		fill(mat[i], mat[i] + n, MAX/2);
		for(int j = 0; j < k; j ++)
			cin >> b[i][j] >> s[i][j];
	}
	for(int i = 0; i < m; i ++){
		int u, v;
      	ll w;
		cin >> u >> v >> w, u --, v --;
		mat[u][v] = w;
	}
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			for(int t = 0; t < n; t ++)
				mat[j][t] = min(mat[j][t], mat[j][i] + mat[i][t]);

	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			for(int t = 0; t < k; t ++)
				if( s[j][t] != -1 && b[i][t] != -1)
					res[i][j] = max(res[i][j], s[j][t] - b[i][t]);
	
	ll l = 0, r = MAX/2, ans = MAX/2;
	while( l <= r){
		ll mid = (l + r)/2;
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < n; j ++)
				tmp[i][j] = mid*min(mat[i][j], MAX/2*mid) - res[i][j];
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < n; j ++)
				for(int t = 0; t < n; t ++)
					tmp[j][t] = min(tmp[j][t], tmp[j][i] + tmp[i][t]);
		bool dor = false;
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < n; j ++)
				for(int t = 0; t < n; t ++)
					if( tmp[j][t] > tmp[j][i] + tmp[i][t])
						dor = true;
		if( dor ) l = mid + 1;
		else r = mid - 1, ans = min(ans, mid);
	}
	cout << ans << endl;

	return 0;
}

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