#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MAXN = 1e2 + 7;
constexpr ll oo = 8e18;
ll dist[MAXN][MAXN];
ll profit[MAXN][MAXN];
ll cycle[MAXN][MAXN];
pair<ll, ll> market[MAXN][1007];
int n, m, k;
void computeDist(){
for(int l = 1; l <= n; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][l] != oo && dist[l][j] != oo)
dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]);
}
void computeProfit(){
for(int l = 1; l <= k; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(market[i][l].first != -1 && market[j][l].second != -1 && dist[i][j] != oo && i != j)
profit[i][j] = max(profit[i][j], market[j][l].second - market[i][l].first);
}
void prepare(ll x){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(dist[i][j] != oo)
cycle[i][j] = (dist[i][j] * x) - profit[i][j];
else cycle[i][j] = oo;
}
}
}
bool check(ll x){
prepare(x);
for(int l = 1; l <= n; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][l] != oo && dist[l][j] != oo)
cycle[i][j] = min(cycle[i][j], cycle[i][l] + cycle[l][j]);
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cout << "i: " << i << " j " << j << " cycle: " << cycle[i][j] << "\n";
for(int l = 1; l <= n; l++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][l] != oo && dist[l][j] != oo)
if(cycle[i][j] > cycle[i][l] + cycle[l][j]) return true;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][j] != oo && dist[j][i] != oo && i != j)
if(cycle[i][j] + cycle[j][i] <= 0) return true;
*/
for(int i = 1; i <= n; i++)
if(cycle[i][i] <= 0) return true;
return false;
}
ll BS(){
ll l = 0, r = 1e9, mid;
while(l < r){
mid = (l+r)/2;
if(check(mid)) l = mid + 1;
else r = mid;
}
if(check(l)) return l;
return max(--l, (ll)0);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= k; j++)
cin >> market[i][j].first >> market[i][j].second;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dist[i][j] = oo;
for(int i = 1; i <= m; i++){
int u, v;
ll t;
cin >> u >> v >> t;
dist[u][v] = min(dist[u][v], t);
}
computeDist();
computeProfit();
/*
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cout << "i " << i << " j " << j << " profit " << profit[i][j] << "\n";
check(1);
cout << "\n";
check(2);
cout << "\n";
check(3);
cout << "\n";
check(4);
cout << "\n";
*/
cout << BS() << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
3456 KB |
Output is correct |
2 |
Correct |
35 ms |
1028 KB |
Output is correct |
3 |
Correct |
35 ms |
860 KB |
Output is correct |
4 |
Correct |
5 ms |
600 KB |
Output is correct |
5 |
Correct |
5 ms |
604 KB |
Output is correct |
6 |
Correct |
5 ms |
604 KB |
Output is correct |
7 |
Correct |
5 ms |
604 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
5 ms |
604 KB |
Output is correct |
10 |
Correct |
5 ms |
604 KB |
Output is correct |
11 |
Correct |
5 ms |
760 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
5 ms |
824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
604 KB |
Output is correct |
2 |
Correct |
5 ms |
604 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
5 ms |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
604 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
5 ms |
824 KB |
Output is correct |
9 |
Correct |
6 ms |
604 KB |
Output is correct |
10 |
Correct |
5 ms |
604 KB |
Output is correct |
11 |
Correct |
5 ms |
848 KB |
Output is correct |
12 |
Correct |
4 ms |
604 KB |
Output is correct |
13 |
Correct |
5 ms |
732 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
4 ms |
604 KB |
Output is correct |
16 |
Correct |
6 ms |
604 KB |
Output is correct |
17 |
Correct |
5 ms |
800 KB |
Output is correct |
18 |
Correct |
5 ms |
604 KB |
Output is correct |
19 |
Correct |
5 ms |
692 KB |
Output is correct |
20 |
Correct |
6 ms |
888 KB |
Output is correct |
21 |
Correct |
5 ms |
600 KB |
Output is correct |
22 |
Correct |
7 ms |
600 KB |
Output is correct |
23 |
Correct |
5 ms |
860 KB |
Output is correct |
24 |
Correct |
5 ms |
784 KB |
Output is correct |
25 |
Correct |
5 ms |
860 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
7 ms |
856 KB |
Output is correct |
28 |
Correct |
5 ms |
860 KB |
Output is correct |
29 |
Correct |
6 ms |
852 KB |
Output is correct |
30 |
Correct |
5 ms |
604 KB |
Output is correct |
31 |
Correct |
5 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
860 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
7 ms |
856 KB |
Output is correct |
4 |
Correct |
5 ms |
860 KB |
Output is correct |
5 |
Correct |
6 ms |
852 KB |
Output is correct |
6 |
Correct |
5 ms |
604 KB |
Output is correct |
7 |
Correct |
5 ms |
604 KB |
Output is correct |
8 |
Correct |
38 ms |
1624 KB |
Output is correct |
9 |
Correct |
63 ms |
4048 KB |
Output is correct |
10 |
Correct |
37 ms |
1112 KB |
Output is correct |
11 |
Correct |
42 ms |
1372 KB |
Output is correct |
12 |
Correct |
37 ms |
1368 KB |
Output is correct |
13 |
Correct |
36 ms |
1268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
604 KB |
Output is correct |
2 |
Correct |
5 ms |
604 KB |
Output is correct |
3 |
Correct |
5 ms |
848 KB |
Output is correct |
4 |
Correct |
4 ms |
604 KB |
Output is correct |
5 |
Correct |
5 ms |
732 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
4 ms |
604 KB |
Output is correct |
8 |
Correct |
6 ms |
604 KB |
Output is correct |
9 |
Correct |
5 ms |
800 KB |
Output is correct |
10 |
Correct |
5 ms |
604 KB |
Output is correct |
11 |
Correct |
5 ms |
692 KB |
Output is correct |
12 |
Correct |
6 ms |
888 KB |
Output is correct |
13 |
Correct |
5 ms |
600 KB |
Output is correct |
14 |
Correct |
7 ms |
600 KB |
Output is correct |
15 |
Correct |
5 ms |
860 KB |
Output is correct |
16 |
Correct |
5 ms |
784 KB |
Output is correct |
17 |
Correct |
38 ms |
1624 KB |
Output is correct |
18 |
Correct |
63 ms |
4048 KB |
Output is correct |
19 |
Correct |
37 ms |
1112 KB |
Output is correct |
20 |
Correct |
42 ms |
1372 KB |
Output is correct |
21 |
Correct |
37 ms |
1368 KB |
Output is correct |
22 |
Correct |
36 ms |
1268 KB |
Output is correct |
23 |
Correct |
5 ms |
860 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
7 ms |
856 KB |
Output is correct |
26 |
Correct |
5 ms |
860 KB |
Output is correct |
27 |
Correct |
6 ms |
852 KB |
Output is correct |
28 |
Correct |
5 ms |
604 KB |
Output is correct |
29 |
Correct |
5 ms |
604 KB |
Output is correct |
30 |
Correct |
57 ms |
3456 KB |
Output is correct |
31 |
Correct |
35 ms |
1028 KB |
Output is correct |
32 |
Correct |
35 ms |
860 KB |
Output is correct |
33 |
Correct |
5 ms |
600 KB |
Output is correct |
34 |
Correct |
5 ms |
604 KB |
Output is correct |
35 |
Correct |
5 ms |
604 KB |
Output is correct |
36 |
Correct |
5 ms |
604 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
5 ms |
604 KB |
Output is correct |
39 |
Correct |
5 ms |
604 KB |
Output is correct |
40 |
Correct |
5 ms |
760 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
5 ms |
824 KB |
Output is correct |
43 |
Correct |
35 ms |
1152 KB |
Output is correct |
44 |
Correct |
37 ms |
1372 KB |
Output is correct |
45 |
Correct |
48 ms |
2944 KB |
Output is correct |
46 |
Correct |
36 ms |
1116 KB |
Output is correct |
47 |
Correct |
37 ms |
1116 KB |
Output is correct |
48 |
Correct |
37 ms |
1368 KB |
Output is correct |
49 |
Correct |
63 ms |
3924 KB |
Output is correct |
50 |
Correct |
0 ms |
456 KB |
Output is correct |
51 |
Correct |
0 ms |
348 KB |
Output is correct |
52 |
Correct |
34 ms |
1128 KB |
Output is correct |
53 |
Correct |
37 ms |
1116 KB |
Output is correct |
54 |
Correct |
32 ms |
1112 KB |
Output is correct |
55 |
Correct |
33 ms |
1116 KB |
Output is correct |
56 |
Correct |
35 ms |
860 KB |
Output is correct |
57 |
Correct |
0 ms |
348 KB |
Output is correct |
58 |
Correct |
6 ms |
968 KB |
Output is correct |
59 |
Correct |
6 ms |
860 KB |
Output is correct |
60 |
Correct |
6 ms |
976 KB |
Output is correct |
61 |
Correct |
67 ms |
4328 KB |
Output is correct |
62 |
Correct |
66 ms |
4076 KB |
Output is correct |
63 |
Correct |
0 ms |
344 KB |
Output is correct |