Submission #106753

#	Time	Username	Problem	Language	Result	Execution time	Memory
106753		kig9981	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	54 ms	3704 KiB

merchant

#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<vector<pair<int,int>>> I;
long long D[500][500], C[500][500];

long long comp(long long u1, long long d1, long long u2, long long d2)
{
	return u1*d2-u2*d1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, K;
	long long a1=0, a2=1;
	cin>>N>>M>>K;
	I.resize(N);
	memset(D,0x3f,sizeof(D));
	for(int i=0;i<N;i++) {
		I[i].resize(K);
		for(int k=0;k<K;k++) {
			cin>>I[i][k].first>>I[i][k].second;
			for(int j=0;j<i;j++) {
				if(I[i][k].first!=-1) C[i][j]=max(C[i][j],1LL*I[j][k].second-I[i][k].first);
				if(I[j][k].first!=-1) C[j][i]=max(C[j][i],1LL*I[i][k].second-I[j][k].first);
			}
		}
	}
	while(M--) {
		int a, b, w;
		cin>>a>>b>>w; --a; --b;
		D[a][b]=min(D[a][b],1LL*w);
	}
	for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++) D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
	for(int k=0;k<N;k++) for(int i=0;i<N;i++) for(int j=0;j<N;j++) {
		if(D[i][k]==0x3f3f3f3f3f3f3f3f || D[k][j]==0x3f3f3f3f3f3f3f3f) continue;
		if(D[i][j]==0x3f3f3f3f3f3f3f3f || comp(C[i][j],D[i][j],C[i][k]+C[k][j],D[i][k]+D[k][j])<0) {
			C[i][j]=C[i][k]+C[k][j];
			D[i][j]=D[i][k]+D[k][j];
		}
	}
	for(int i=0;i<N;i++) if(comp(a1,a2,C[i][i],D[i][i])<0) {
		a1=C[i][i];
		a2=D[i][i];
	}
	cout<<a1/a2<<'\n';
	return 0;
}

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