이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 101, K = 1001;
const int inf = 1 << 30;
int d[N][N], p[N][N], rp[N][N];
int b[N][K], s[N][K];
int n, m, q;
bool check(int av){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
rp[i][j] = p[i][j] - av * d[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
rp[j][k] = max(rp[j][k], rp[j][i] + rp[i][k]);
}
}
}
for(int i = 0; i < n; i++){
if(rp[i][i] >= 0) return true;
}
return false;
}
int32_t main(){
cin >> n >> m >> q;
for(int i = 0; i < n; i++){
for(int j = 0; j < q; j++){
cin >> b[i][j] >> s[i][j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
d[i][j] = inf;
}
}
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
u--; v--;
d[u][v] = min(d[u][v], w);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < q; k++){
if(s[j][k] != -1 && b[i][k] != -1) p[i][j] = max(p[i][j], s[j][k] - b[i][k]);
}
}
}
int l = 0, r = 1e9;
while(l != r){
int mid = (l + r + 1) / 2;
if(check(mid)){
l = mid;
}else{
r = mid - 1;
}
}
cout << l << endl;
}
# | 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... |