이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e3+5;
int dis[N][N], profit[N][N], b[N][N], s[N][N], dis2[N][N];
int n,m,k;
bool check(int x){
assert(x!=0);
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
dis2[i][j] = x*min(dis[i][j],(int)1e18/x) - profit[i][j];
}
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
dis2[i][j] = min(dis2[i][j],dis2[i][k]+dis2[k][j]);
}
}
}
for(int i = 1;i <= n;i++) if(dis2[i][i] <= 0) return true;
return false;
}
signed main(){
fastio
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
for(int j = 1;j <= n;j++){
dis[i][j] = 1e18;
}
for(int j = 1;j <= k;j++){
cin >> b[i][j] >> s[i][j];
//Meaning that the cost to buy item j in market i
}
}
for(int i = 0;i < m;i++){
int u,v,w;
cin >> u >> v >> w;
dis[u][v] = w;
}
for(int k = 1;k <= n;k++){
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
for(int x = 1; x <= k; x++){
if(s[j][x] == -1 || b[i][x] == -1) continue;
profit[i][j] = max(profit[i][j],s[j][x]-b[i][x]);
}
}
}
int l = 1, r = 1e9;
while(l+1 < r){
//cout << l << " " << r << "\n";
int mid = l+r>>1;
if(!check(mid)) r = mid-1;
else l = mid;
}
if(check(r)) cout << r << "\n";
else if(check(l)) cout << l << "\n";
else cout << 0 << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
merchant.cpp: In function 'int main()':
merchant.cpp:72:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = l+r>>1;
| ~^~
# | 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... |