# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
759290 | boyliguanhan | 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>
#define l long long
#define X(z) x[z][i][j]
#define L F(i,n)F(j,n)
#define F(x,y) for(l x=1;x<=y;++x)
using namespace std;
l n,m,K,x[4][101][1001];
bool C(l t) {
L X(3)=-1e18;
L {
if(i==j||X(0)>1e9)continue;
X(3)=-t*X(0);
F(k,K) {
if(x[1][i][k]<0||x[2][j][k]<0)continue;
X(3)=max(X(3),x[2][j][k]-x[1][i][k]-t*X(0));
}
}
F(k,n)L X(3)=max(X(3),x[3][i][k]+x[3][k][j]);
F(i,n) if(x[3][i][i]>=0)return 1;
return 0;
}
int main() {
cin >> n >> m >> K;
L X(0)=2e9;
F(i,n)F(j,K)cin>>X(1)>>X(2);
F(k,m){
l i,j,c;
cin>>i>>j>>c;
X(0)=min(X(0),c);
}
F(k,n)L X(0)=min(X(0),x[0][i][k]+x[0][k][j]);
l l=0,r=1e9;
while(l<r-1){
if(C(l+r>>1)) l=l+r>>1;
else r=l+r>>1;
}
cout << l<< '\n';
}