#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 1100, maxk = 1010;
const ll inf = 1e17;
int n, m, k;
ll dist[maxn][maxn], b[maxn][maxk], s[maxn][maxk];
ll profit[maxn][maxn], dp[maxn][maxn];
void floyd_warshall()
{
for (int p = 1; p <= n; p ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (dist[i][p] + dist[p][j] < dist[i][j])
{
dist[i][j] = dist[i][p] + dist[p][j];
}
}
}
void bin_floyd()
{
for (int p = 1; p <= n; p ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (dp[i][p] + dp[p][j] < dp[i][j])
{
dp[i][j] = dp[i][p] + dp[p][j];
}
}
}
void build_graph(ll mf)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j ++)
{
if (mf == 0)
dp[i][j] = -profit[i][j];
else
dp[i][j] = mf * min(dist[i][j], inf / mf) - profit[i][j];
///cout << i << " " << j << " " << dp[i][j] << " : " << dist[i][j] << " : " << profit[i][j] << endl;
}
}
bool check(ll mf)
{
build_graph(mf);
bin_floyd();
bool neg = false;
for (int i = 1; i <= n; i ++)
if (dp[i][i] <= 0)
neg = true;
return neg;
}
void solve()
{
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
dist[i][j] = inf;
for (int j = 1; j <= k; j ++)
cin >> b[i][j] >> s[i][j];
}
for (int i = 1; i <= m; i ++)
{
int v, u;
ll w;
cin >> v >> u >> w;
dist[v][u] = min(dist[v][u], w);
}
floyd_warshall();
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
for (int p = 1; p <= k; p ++)
{
if (s[j][p] != -1 && b[i][p] != -1)
{
profit[i][j] = max(profit[i][j], s[j][p] - b[i][p]);
}
}
ll lf = 0, rf = 1e9;
while(lf <= rf)
{
ll mf = (lf + rf) / 2;
if (check(mf))
lf = mf + 1;
else
rf = mf - 1;
}
cout << max((ll)0, rf) << endl;
}
int main()
{
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
89 ms |
2820 KB |
Output is correct |
2 |
Correct |
31 ms |
2004 KB |
Output is correct |
3 |
Correct |
31 ms |
1976 KB |
Output is correct |
4 |
Correct |
7 ms |
1108 KB |
Output is correct |
5 |
Correct |
6 ms |
1108 KB |
Output is correct |
6 |
Correct |
6 ms |
1108 KB |
Output is correct |
7 |
Correct |
7 ms |
1216 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
6 ms |
1168 KB |
Output is correct |
10 |
Correct |
6 ms |
1108 KB |
Output is correct |
11 |
Correct |
6 ms |
1072 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
8 ms |
1216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
1108 KB |
Output is correct |
2 |
Correct |
7 ms |
1216 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
6 ms |
1168 KB |
Output is correct |
5 |
Correct |
6 ms |
1108 KB |
Output is correct |
6 |
Correct |
6 ms |
1072 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
8 ms |
1216 KB |
Output is correct |
9 |
Correct |
7 ms |
1236 KB |
Output is correct |
10 |
Correct |
5 ms |
1108 KB |
Output is correct |
11 |
Correct |
6 ms |
1364 KB |
Output is correct |
12 |
Correct |
6 ms |
1236 KB |
Output is correct |
13 |
Correct |
12 ms |
1416 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
6 ms |
1236 KB |
Output is correct |
16 |
Correct |
7 ms |
1408 KB |
Output is correct |
17 |
Correct |
6 ms |
1236 KB |
Output is correct |
18 |
Correct |
7 ms |
1236 KB |
Output is correct |
19 |
Correct |
12 ms |
1364 KB |
Output is correct |
20 |
Correct |
8 ms |
1364 KB |
Output is correct |
21 |
Correct |
6 ms |
1388 KB |
Output is correct |
22 |
Correct |
7 ms |
1364 KB |
Output is correct |
23 |
Correct |
10 ms |
1420 KB |
Output is correct |
24 |
Correct |
6 ms |
1108 KB |
Output is correct |
25 |
Correct |
14 ms |
1364 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
15 ms |
1364 KB |
Output is correct |
28 |
Correct |
12 ms |
1364 KB |
Output is correct |
29 |
Correct |
12 ms |
1416 KB |
Output is correct |
30 |
Correct |
7 ms |
1388 KB |
Output is correct |
31 |
Correct |
7 ms |
1384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
1364 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
15 ms |
1364 KB |
Output is correct |
4 |
Correct |
12 ms |
1364 KB |
Output is correct |
5 |
Correct |
12 ms |
1416 KB |
Output is correct |
6 |
Correct |
7 ms |
1388 KB |
Output is correct |
7 |
Correct |
7 ms |
1384 KB |
Output is correct |
8 |
Correct |
87 ms |
2676 KB |
Output is correct |
9 |
Correct |
178 ms |
3456 KB |
Output is correct |
10 |
Correct |
76 ms |
2596 KB |
Output is correct |
11 |
Correct |
93 ms |
2684 KB |
Output is correct |
12 |
Correct |
93 ms |
2684 KB |
Output is correct |
13 |
Correct |
46 ms |
2596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
1236 KB |
Output is correct |
2 |
Correct |
5 ms |
1108 KB |
Output is correct |
3 |
Correct |
6 ms |
1364 KB |
Output is correct |
4 |
Correct |
6 ms |
1236 KB |
Output is correct |
5 |
Correct |
12 ms |
1416 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
6 ms |
1236 KB |
Output is correct |
8 |
Correct |
7 ms |
1408 KB |
Output is correct |
9 |
Correct |
6 ms |
1236 KB |
Output is correct |
10 |
Correct |
7 ms |
1236 KB |
Output is correct |
11 |
Correct |
12 ms |
1364 KB |
Output is correct |
12 |
Correct |
8 ms |
1364 KB |
Output is correct |
13 |
Correct |
6 ms |
1388 KB |
Output is correct |
14 |
Correct |
7 ms |
1364 KB |
Output is correct |
15 |
Correct |
10 ms |
1420 KB |
Output is correct |
16 |
Correct |
6 ms |
1108 KB |
Output is correct |
17 |
Correct |
87 ms |
2676 KB |
Output is correct |
18 |
Correct |
178 ms |
3456 KB |
Output is correct |
19 |
Correct |
76 ms |
2596 KB |
Output is correct |
20 |
Correct |
93 ms |
2684 KB |
Output is correct |
21 |
Correct |
93 ms |
2684 KB |
Output is correct |
22 |
Correct |
46 ms |
2596 KB |
Output is correct |
23 |
Correct |
14 ms |
1364 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
15 ms |
1364 KB |
Output is correct |
26 |
Correct |
12 ms |
1364 KB |
Output is correct |
27 |
Correct |
12 ms |
1416 KB |
Output is correct |
28 |
Correct |
7 ms |
1388 KB |
Output is correct |
29 |
Correct |
7 ms |
1384 KB |
Output is correct |
30 |
Correct |
89 ms |
2820 KB |
Output is correct |
31 |
Correct |
31 ms |
2004 KB |
Output is correct |
32 |
Correct |
31 ms |
1976 KB |
Output is correct |
33 |
Correct |
7 ms |
1108 KB |
Output is correct |
34 |
Correct |
6 ms |
1108 KB |
Output is correct |
35 |
Correct |
6 ms |
1108 KB |
Output is correct |
36 |
Correct |
7 ms |
1216 KB |
Output is correct |
37 |
Correct |
1 ms |
304 KB |
Output is correct |
38 |
Correct |
6 ms |
1168 KB |
Output is correct |
39 |
Correct |
6 ms |
1108 KB |
Output is correct |
40 |
Correct |
6 ms |
1072 KB |
Output is correct |
41 |
Correct |
1 ms |
468 KB |
Output is correct |
42 |
Correct |
8 ms |
1216 KB |
Output is correct |
43 |
Correct |
42 ms |
2280 KB |
Output is correct |
44 |
Correct |
40 ms |
2748 KB |
Output is correct |
45 |
Correct |
63 ms |
3800 KB |
Output is correct |
46 |
Correct |
47 ms |
2644 KB |
Output is correct |
47 |
Correct |
37 ms |
2720 KB |
Output is correct |
48 |
Correct |
37 ms |
2644 KB |
Output is correct |
49 |
Correct |
162 ms |
5328 KB |
Output is correct |
50 |
Correct |
1 ms |
468 KB |
Output is correct |
51 |
Correct |
1 ms |
436 KB |
Output is correct |
52 |
Correct |
35 ms |
2176 KB |
Output is correct |
53 |
Correct |
38 ms |
2300 KB |
Output is correct |
54 |
Correct |
35 ms |
2388 KB |
Output is correct |
55 |
Correct |
33 ms |
2244 KB |
Output is correct |
56 |
Correct |
32 ms |
2108 KB |
Output is correct |
57 |
Correct |
1 ms |
308 KB |
Output is correct |
58 |
Correct |
13 ms |
1544 KB |
Output is correct |
59 |
Correct |
11 ms |
1468 KB |
Output is correct |
60 |
Correct |
11 ms |
1476 KB |
Output is correct |
61 |
Correct |
149 ms |
5324 KB |
Output is correct |
62 |
Correct |
156 ms |
5384 KB |
Output is correct |
63 |
Correct |
1 ms |
340 KB |
Output is correct |