이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
using namespace std;
const int N = 100 + 2, M = 9900 + 4, K = 1000 + 3, inf = 1e9 + 7;
const ll inf2 = 2e18;
int n, m, k;
int b[N][K], s[N][K];
ll d[N][N];
int w[N][N];
void prep() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int kk = 0; kk < k; ++kk) if (~b[i][kk] && ~s[j][kk])
w[i][j] = max(w[i][j], s[j][kk] - b[i][kk]);
for (int kk = 1; kk <= n; ++kk)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) if (d[i][kk] && d[kk][j])
d[i][j] = min(d[i][j], d[i][kk] + d[kk][j]);
}
ll dist[N][N];
void maxi(ll &a, ll b) { if (a < b) a = b; }
bool check(ll x) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dist[i][j] = d[i][j] ? w[i][j] - d[i][j] * x : -inf2;
for (int kk = 1; kk <= n; ++kk)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
maxi(dist[i][j], dist[i][kk] + dist[kk][j]);
for (int i = 1; i <= n; ++i)
if (dist[i][i] >= 0) return true;
return false;
}
int main() {
cin.tie(NULL)->sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < k; ++j)
cin >> b[i][j] >> s[i][j];
for (int i = 0, a, b; i < m; ++i) {
cin >> a >> b;
cin >> d[a][b];
}
prep();
int lo(0), hi(inf), mid;
while (lo <= hi) {
mid = (lo + hi) >> 1;
if (check(mid))
lo = mid + 1;
else hi = mid - 1;
}
cout << lo - 1 << '\n';
}
/** /\_/\
* (= ._.)
* / >0 \>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... |