Submission #407110

#	Time	Username	Problem	Language	Result	Execution time	Memory
407110		inluminas	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	77 ms	3780 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],hor[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]=hor[i][j]=inf;
		dis[i][i]=hor[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		dis[u][v]=min(dis[u][v],w);
		hor[u][v]=dis[u][v];
	}
	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];
					hor[i][j]=dis[i][j];
				}
			}
		}
	}
	for(int item=1;item<=k;item++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j || dis[i][j]==inf || b[i][item]==-1 || s[j][item]==-1 || b[i][item]>=s[j][item]) continue;
				double now=(double)lob[i][j]/(double)hor[i][j];
				double res=(double)(s[j][item]-b[i][item])/(double)(dis[i][j]);
				if(now>=res) continue;
				lob[i][j]=s[j][item]-b[i][item];
			}
		}
	}

	for(int l=1;l<=n;l++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j || dis[i][j]==inf || dis[i][l]==inf || dis[l][j]==inf) continue;
				if(dis[i][l]+dis[l][j]!=dis[i][j]) continue;
				double now=(double)lob[i][j]/(double)hor[i][j];
				double res=(lob[i][l]+lob[l][j])/(double)(hor[i][l]+hor[l][j]);
				if(now>=res) continue;
				hor[i][j]=hor[i][l]+hor[l][j],lob[i][j]=lob[i][l]+lob[l][j];
			}
		}
	}

	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) continue;
			if(dis[i][j]==inf || dis[j][i]==inf) continue;
			ll res=(lob[i][j]+lob[j][i])/(hor[i][j]+hor[j][i]);
			ans=max(ans,res);
		}
	}
	cout<<ans<<endl;
	return 0;
}

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