# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
759290 | boyliguanhan | 여행하는 상인 (APIO17_merchant) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}