#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("trapv")
typedef long long ll;
const ll inf = 1e16;
const int MAXN = 100 + 25;
ll s[MAXN][1001], b[MAXN][1001], n, m, k;
ll adj[MAXN][MAXN], adj2[MAXN][MAXN], val[MAXN][MAXN];
bool check (ll x) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj2[i][j] = min(inf / x, adj[i][j]) * x - val[i][j];
}
}
bool flag = 0;
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj2[i][j] = min(adj2[i][j], adj2[i][l] + adj2[l][j]);
}
}
}
for (int i = 1; i <= n; i++) flag |= adj2[i][i] <= 0ll;
return !flag;
}
int main () {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) for (int j = 1; j <= k; j++) cin >> b[i][j] >> s[i][j];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj[i][j] = inf;
}
}
while (m--) {
ll a, b, c; cin >> a >> b >> c;
adj[a][b] = min(adj[a][b], c);
}
for (int l = 1; l <= n; l++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
adj[i][j] = min(adj[i][j], adj[i][l] + adj[l][j]);
}
}
}
for (int l = 1; l <= k; l++) {
for (int i = 1; i <= n; i++) {
if (b[i][l] == -1) continue;
for (int j = 1; j <= n; j++) {
if (s[j][l] != -1) val[i][j] = max(val[i][j], s[j][l] - b[i][l]);
}
}
}
ll l = 1, r = 1e9, ans = -1;
while (l <= r) {
ll mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
145 ms |
4580 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
4696 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
85 ms |
4928 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
4696 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |