# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
406975 | Waratpp123 | 여행하는 상인 (APIO17_merchant) | C++14 | 119 ms | 2116 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
long long buy[105][1005],sell[105][1005],dis[105][105],prof[105][105],eff[105][105];
int main(){
long long i,j,n,m,k,p,u,v,w,l,r,mid;
scanf("%lld %lld %lld",&n,&m,&p);
for(i=1;i<=n;i++){
for(j=1;j<=p;j++){
scanf("%lld %lld",&buy[i][j],&sell[i][j]);
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
dis[i][j]=2e18;
prof[i][j]=0;
}
}
for(i=1;i<=m;i++){
scanf("%lld %lld %lld",&u,&v,&w);
dis[u][v]=w;
}
for(k=1;k<=n;k++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(dis[i][j]>1e18){
prof[i][j]=-1;
continue;
}
int ch=0;
for(k=1;k<=p;k++){
if(sell[j][k]!=-1&&buy[i][k]!=-1) ch=1,prof[i][j]=max(prof[i][j],sell[j][k]-buy[i][k]);
}
if(ch==0) prof[i][j]=-1;
}
}
l=0,r=1e9;
while(l<r){
mid=(l+r+1)/2;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(prof[i][j]==-1) eff[i][j]=-1e18;
else eff[i][j]=prof[i][j]-mid*dis[i][j];
}
}
for(k=1;k<=n;k++){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(prof[i][j]==-1||prof[i][k]==-1||prof[k][j]==-1||i==k||j==k) continue;
eff[i][j]=max(eff[i][j],eff[i][k]+eff[k][j]);
}
}
}
int ch=0;
for(i=1;i<=n;i++) if(eff[i][i]>=0) ch=1;
if(ch==1) l=mid;
else r=mid-1;
}
printf("%lld\n",l);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |