Submission #407120

#	Time	Username	Problem	Language	Result	Execution time	Memory
407120		inluminas	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	232 ms	1996 KiB

merchant

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

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)

const int lmt=1e3+2,lmt2=1e2+2;
const ll inf=1e18;
int n,m,k;
ll b[lmt2][lmt],s[lmt2][lmt],dis[lmt2][lmt2],ok[lmt2][lmt2],lob[lmt2][lmt2];

int main(){
	fastio;

	cin>>n>>m>>k;
	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<=n;i++){
		for(int j=1;j<=n;j++) dis[i][j]=inf;
	}
	for(int i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		dis[u][v]=min(dis[u][v],w);
	}
	for(int l=1;l<=n;l++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][j]>dis[i][l]+dis[l][j]){
					dis[i][j]=dis[i][l]+dis[l][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(dis[i][j]==inf){
				lob[i][j]=-inf;
				continue;
			}
			for(int item=1;item<=k;item++){
				if(s[j][item]==-1 || b[i][item]==-1) continue;
				lob[i][j]=max(lob[i][j],s[j][item]-b[i][item]);
			}
		}
	}
	ll lo=0,hi=1e18;
	while(hi-lo>1){
		ll mid=(lo+hi)/2;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][j]==inf) ok[i][j]=-inf;
				else ok[i][j]=lob[i][j]-mid*dis[i][j];
			}
		}
		for(int l=1;l<=n;l++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(dis[i][l]==inf || dis[j][l]==inf || dis[i][l]+dis[l][j]!=dis[i][j]) continue;
					ok[i][j]=max(ok[i][j],ok[i][l]+ok[l][j]);
				}
			}
		}
		bool on=0;
		for(int i=1;i<=n;i++){
			if(ok[i][i]>=0){
				on=1;
				break;
			}
		}
		if(on) lo=mid;
		else hi=mid-1;
	}
	cout<<lo<<endl;
}

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