이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll di[105][105], gain[105][105], b[105][1005], s[105][1005];
pair<ll, ll> opt[105][105];
const ll inf = 1e18;
int main () {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) di[i][j] = inf;
for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) {
cin >> b[i][j] >> s[i][j];
if (b[i][j] == -1) b[i][j] = inf;
if (s[i][j] == -1) s[i][j] = -inf;
}
while (m--) {
int u, v;
ll t;
cin >> u >> v >> t;
di[u][v] = t;
}
for (int t = 1; t <= n; t++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) di[i][j] = min(di[i][j], di[i][t] + di[t][j]);
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
gain[i][j] = 0;
for (int a = 1; a <= k; a++) gain[i][j] = max(gain[i][j], s[j][a] - b[i][a]);
if (gain[i][j]) opt[i][j] = {gain[i][j], di[i][j]};
}
for (int t = 1; t <= n; t++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (t != i && t != j && (!opt[i][j].second || (gain[i][t] + gain[t][j]) * opt[i][j].second > (di[i][t] + di[t][j]) * opt[i][j].first)) opt[i][j] = {gain[i][t] + gain[t][j], di[i][t] + di[t][j]};
ll ans = 0;
for (int i = 1; i <= n; i++) if (opt[i][i].second) ans = max(ans, opt[i][i].first / opt[i][i].second);
cout << ans << '\n';
return 0;
}
# | 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... |