#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
#define endl "\n"
#define sp <<" "<<
#define INF 1e9+21
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
void solution() {
ll n, m, k; cin >> n >> m >> k;
vector<vector<pair<ll, ll>>> bs(n, vector<pair<ll, ll>>(k)); // haha bs
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < k; j++) {
cin >> bs[i][j].first >> bs[i][j].second;
}
}
ll dist[n+5][n+5];
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
dist[i][j] = INF;
}
}
for (ll i = 0; i < m; i++) {
ll v, w, t; cin >> v >> w >> t;
v--; w--;
dist[v][w] = t;
}
// dist between any two nodes
for (ll l = 0; l < n; l++) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
}
}
}
// profit between any two nodes
ll profit[n+5][n+5];
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
profit[i][j] = 0;
for (ll l = 0; l < k; l++) {
if (bs[i][l].first == -1 || bs[j][l].second == -1) continue;
profit[i][j] = max(profit[i][j], bs[j][l].second - bs[i][l].first);
}
}
}
// binary search max efficiency
ll eff[n+5][n+5];
ll l = 1, r = 1e11+21;
while (l < r) {
ll mid = (l + r) / 2;
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
eff[i][j] = min(mid * dist[i][j] - profit[i][j], (ll)INF);
}
}
// floyd warshall again
for (ll kk = 0; kk < n; kk++) {
for (ll i = 0; i < n; i++) {
for (ll j = 0; j < n; j++) {
eff[i][j] = min(eff[i][j], eff[i][kk] + eff[kk][j]);
}
}
}
bool flag = false;
for (ll i = 0; i < n; i++) {
if (eff[i][i] <= 0) {
flag = true;
break;
}
}
if (flag) {
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << r << endl;
return;
}
signed main() {
fast_io();
solution();
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... |