#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define info() cerr << __PRETTY_FUNCTION__ << ": " << __LINE__ << endl
void abc() {cerr << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cerr << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
};
template <typename T> struct vvv : vector <vv <T>> {
vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
};
#ifdef Doludu
#define test(args...) info(), abc("[" + string(#args) + "]", args)
#define owo
#else
#define test(args...)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 998244353, N = 1000001, logN = 20, K = 111;
int main () {
owo;
int n, m, k;
cin >> n >> m >> k;
vv <pii> a(n, k, mp(0, 0));
for (int i = 0; i < n; ++i) for (int j = 0; j < k; ++j) cin >> a[i][j];
vv <int> dis(n, n, 1e9 + 87);
vv <long long> profit(n, n, 0);
for (int i = 0; i < n; ++i) dis[i][i] = 0;
for (int i = 0, u, v, w; i < m; ++i) {
cin >> u >> v >> w, --u, --v;
dis[u][v] = min(dis[u][v], w);
}
for (int k = 0; k < n; ++k) for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
for (int t = 0; t < k; ++t) {
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
if (a[i][t].X == -1 || a[j][t].Y == -1) continue;
profit[i][j] = max(profit[i][j], (long long)a[j][t].Y - a[i][t].X);
}
}
auto chk = [&](long long x) {
vv <long long> d(n, n, 1ll << 60);
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) {
if (i == j) d[i][j] = 1;
else {
d[i][j] = x * dis[i][j] - profit[i][j];
}
}
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]);
if (i == j && d[i][j] <= 0) return true;
}
return false;
};
long long l = 0, r = 1 << 30;
while (r - l > 1) {
long long mid = l + r >> 1;
if (chk(mid)) l = mid;
else r = mid;
}
cout << l << endl;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/
Compilation message
merchant.cpp: In function 'int main()':
merchant.cpp:84:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | long long mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
109 ms |
1228 KB |
Output is correct |
2 |
Correct |
71 ms |
504 KB |
Output is correct |
3 |
Correct |
35 ms |
460 KB |
Output is correct |
4 |
Correct |
10 ms |
380 KB |
Output is correct |
5 |
Correct |
9 ms |
332 KB |
Output is correct |
6 |
Correct |
10 ms |
332 KB |
Output is correct |
7 |
Correct |
7 ms |
388 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
7 ms |
332 KB |
Output is correct |
10 |
Correct |
10 ms |
372 KB |
Output is correct |
11 |
Correct |
7 ms |
384 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
13 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
332 KB |
Output is correct |
2 |
Correct |
7 ms |
388 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
7 ms |
332 KB |
Output is correct |
5 |
Correct |
10 ms |
372 KB |
Output is correct |
6 |
Correct |
7 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
13 ms |
332 KB |
Output is correct |
9 |
Correct |
9 ms |
332 KB |
Output is correct |
10 |
Correct |
8 ms |
332 KB |
Output is correct |
11 |
Correct |
13 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
384 KB |
Output is correct |
13 |
Correct |
11 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
7 ms |
312 KB |
Output is correct |
16 |
Correct |
8 ms |
332 KB |
Output is correct |
17 |
Correct |
6 ms |
384 KB |
Output is correct |
18 |
Correct |
8 ms |
400 KB |
Output is correct |
19 |
Correct |
9 ms |
440 KB |
Output is correct |
20 |
Correct |
8 ms |
432 KB |
Output is correct |
21 |
Correct |
10 ms |
384 KB |
Output is correct |
22 |
Correct |
12 ms |
368 KB |
Output is correct |
23 |
Correct |
12 ms |
332 KB |
Output is correct |
24 |
Correct |
8 ms |
332 KB |
Output is correct |
25 |
Correct |
9 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
9 ms |
388 KB |
Output is correct |
28 |
Correct |
10 ms |
332 KB |
Output is correct |
29 |
Correct |
14 ms |
384 KB |
Output is correct |
30 |
Correct |
6 ms |
332 KB |
Output is correct |
31 |
Correct |
7 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
9 ms |
388 KB |
Output is correct |
4 |
Correct |
10 ms |
332 KB |
Output is correct |
5 |
Correct |
14 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
332 KB |
Output is correct |
7 |
Correct |
7 ms |
332 KB |
Output is correct |
8 |
Correct |
81 ms |
584 KB |
Output is correct |
9 |
Correct |
131 ms |
1208 KB |
Output is correct |
10 |
Correct |
92 ms |
460 KB |
Output is correct |
11 |
Correct |
96 ms |
520 KB |
Output is correct |
12 |
Correct |
78 ms |
632 KB |
Output is correct |
13 |
Correct |
53 ms |
536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
332 KB |
Output is correct |
2 |
Correct |
8 ms |
332 KB |
Output is correct |
3 |
Correct |
13 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
384 KB |
Output is correct |
5 |
Correct |
11 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
7 ms |
312 KB |
Output is correct |
8 |
Correct |
8 ms |
332 KB |
Output is correct |
9 |
Correct |
6 ms |
384 KB |
Output is correct |
10 |
Correct |
8 ms |
400 KB |
Output is correct |
11 |
Correct |
9 ms |
440 KB |
Output is correct |
12 |
Correct |
8 ms |
432 KB |
Output is correct |
13 |
Correct |
10 ms |
384 KB |
Output is correct |
14 |
Correct |
12 ms |
368 KB |
Output is correct |
15 |
Correct |
12 ms |
332 KB |
Output is correct |
16 |
Correct |
8 ms |
332 KB |
Output is correct |
17 |
Correct |
81 ms |
584 KB |
Output is correct |
18 |
Correct |
131 ms |
1208 KB |
Output is correct |
19 |
Correct |
92 ms |
460 KB |
Output is correct |
20 |
Correct |
96 ms |
520 KB |
Output is correct |
21 |
Correct |
78 ms |
632 KB |
Output is correct |
22 |
Correct |
53 ms |
536 KB |
Output is correct |
23 |
Correct |
9 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
9 ms |
388 KB |
Output is correct |
26 |
Correct |
10 ms |
332 KB |
Output is correct |
27 |
Correct |
14 ms |
384 KB |
Output is correct |
28 |
Correct |
6 ms |
332 KB |
Output is correct |
29 |
Correct |
7 ms |
332 KB |
Output is correct |
30 |
Correct |
109 ms |
1228 KB |
Output is correct |
31 |
Correct |
71 ms |
504 KB |
Output is correct |
32 |
Correct |
35 ms |
460 KB |
Output is correct |
33 |
Correct |
10 ms |
380 KB |
Output is correct |
34 |
Correct |
9 ms |
332 KB |
Output is correct |
35 |
Correct |
10 ms |
332 KB |
Output is correct |
36 |
Correct |
7 ms |
388 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
7 ms |
332 KB |
Output is correct |
39 |
Correct |
10 ms |
372 KB |
Output is correct |
40 |
Correct |
7 ms |
384 KB |
Output is correct |
41 |
Correct |
1 ms |
204 KB |
Output is correct |
42 |
Correct |
13 ms |
332 KB |
Output is correct |
43 |
Correct |
48 ms |
540 KB |
Output is correct |
44 |
Correct |
48 ms |
680 KB |
Output is correct |
45 |
Correct |
83 ms |
1292 KB |
Output is correct |
46 |
Correct |
54 ms |
664 KB |
Output is correct |
47 |
Correct |
65 ms |
652 KB |
Output is correct |
48 |
Correct |
51 ms |
652 KB |
Output is correct |
49 |
Correct |
136 ms |
1464 KB |
Output is correct |
50 |
Correct |
1 ms |
204 KB |
Output is correct |
51 |
Correct |
1 ms |
308 KB |
Output is correct |
52 |
Correct |
59 ms |
528 KB |
Output is correct |
53 |
Correct |
86 ms |
564 KB |
Output is correct |
54 |
Correct |
67 ms |
572 KB |
Output is correct |
55 |
Correct |
56 ms |
552 KB |
Output is correct |
56 |
Correct |
54 ms |
460 KB |
Output is correct |
57 |
Correct |
1 ms |
204 KB |
Output is correct |
58 |
Correct |
14 ms |
496 KB |
Output is correct |
59 |
Correct |
14 ms |
440 KB |
Output is correct |
60 |
Correct |
14 ms |
500 KB |
Output is correct |
61 |
Correct |
117 ms |
1516 KB |
Output is correct |
62 |
Correct |
141 ms |
1520 KB |
Output is correct |
63 |
Correct |
1 ms |
256 KB |
Output is correct |