Submission #1307424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307424		namhh	Travelling Merchant (APIO17_merchant)	C++20	33 / 100	61 ms	3004 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e3+5;
int n,m,k;
int b[N][N],s[N][N],d[N][N][2],w[N][N];
void floyd(int type){
	for(int l = 1; l <= n; l++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++) d[i][j][type] = min(d[i][j][type],d[i][l][type]+d[l][j][type]);
		}
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++) d[i][j][0] = 1e18;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= k; j++) cin >> b[i][j] >> s[i][j];
	}
	for(int i = 1; i <= m; i++){
		int u,v,w;
		cin >> u >> v >> w;
		d[u][v][0] = w;
	}
	floyd(0);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int l = 1; l <= k; l++){
				if(b[i][l] != -1 && s[j][l] != -1) w[i][j] = max(w[i][j],s[j][l]-b[i][l]);
			}
		}
	}
	int l = 1;
	int r = 1e9;
	int ans;
	while(l <= r){
		int mid = (l+r)/2;
		for(int i = 1; i <= n; i++){
		    for(int j = 1; j <= n; j++) d[i][j][1] = mid*min(d[i][j][0],(int)1e18/mid)-w[i][j];
	    }
	    floyd(1);
	    bool ck = false;
	    for(int i = 1; i <= n; i++){
	    	if(d[i][i][1] <= 0){
	    		ck = true;
	    		break;
			}
		}
		if(ck){
			ans = mid;
			l = mid+1;
		}
		else r = mid-1;
	}
	cout << ans;
}
	

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