| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 106751 | kig9981 | Travelling Merchant (APIO17_merchant) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(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;
}