이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 3, INF = 1000 * 1000 * 1000 + 123;
int n, m, kk, d[MAXN][MAXN], b[MAXN][MAXN], s[MAXN][MAXN];
double ans;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j) d[i][j] = INF;
cin >> n >> m >> kk;
for (int i = 0; i < n; i++) for (int j = 0; j < kk; j++) cin >> b[i][j] >> s[i][j];
for (int i = 1; i < n; i++) for (int j = 0; j < kk; j++) if (b[i][j] != -1) return 0;
{
int v, w, t;
for (int i = 0; i < m; i++) {
cin >> v >> w >> t;
d[--v][--w] = t;
}
}
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (int i = 0; i < n; i++) for (int j = 0; j < kk; j++) if (~b[0][j] && ~s[i][j]) ans = max(ans, 1. * (s[i][j] - b[0][j]) / (d[0][i] + d[i][0]));
cout << (int)ans;
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... |