#include <bits/stdc++.h>
#define MAXN 107
#define MAXK 1007
using namespace std;
long long bp[MAXN][MAXK],sp[MAXN][MAXK],d[MAXN][MAXN],w[MAXN][MAXN],wb[MAXN][MAXN],dist[MAXN],dn[MAXN];
int n,m,a;
void zvonocovek()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(i!=j && wb[i][j])
dist[j]=min(dist[j],dist[i]+wb[i][j]);
}
bool provera(long long k)
{
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
{
if(40000000000000000LL/n<d[i][j]*k-w[i][j]) wb[i][j]=0;
else wb[i][j]=n*(d[i][j]*k-w[i][j])-1;
}
dist[1]=0;
for(int i=2;i<=n;i++) dist[i]=1000000000000000000LL;
for(int i=1;i<=n;i++) zvonocovek();
for(int i=1;i<=n;i++) dn[i]=dist[i];
zvonocovek();
for(int i=1;i<=n;i++) if(dist[i]!=dn[i]) return true;
return false;
}
long long binarna(long long l, long long r)
{
if(l==r) return l;
long long s=(l+r+1)/2;
if(provera(s)) return binarna(s,r);
return binarna(l,s-1);
}
int main()
{
cin>>n>>m>>a;
for(int i=1;i<=n;i++) for(int j=1;j<=a;j++) cin>>bp[i][j]>>sp[i][j];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=1000000000000000000LL;
for(int i=1;i<=m;i++)
{
int t1,t2; long long t3;
cin>>t1>>t2>>t3;
d[t1][t2]=min(d[t1][t2],t3);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(i!=j)
for(int k=1;k<=a;k++) if(bp[i][k]!=-1 && sp[j][k]!=-1)
w[i][j]=max(w[i][j],sp[j][k]-bp[i][k]);
//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) printf("%d %d %lld %lld\n",i,j,d[i][j],w[i][j]);
printf("%lld",binarna(0,1000000000));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
2040 KB |
Output is correct |
2 |
Correct |
50 ms |
1380 KB |
Output is correct |
3 |
Correct |
47 ms |
1344 KB |
Output is correct |
4 |
Correct |
9 ms |
888 KB |
Output is correct |
5 |
Correct |
9 ms |
760 KB |
Output is correct |
6 |
Correct |
8 ms |
888 KB |
Output is correct |
7 |
Correct |
11 ms |
892 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
9 ms |
760 KB |
Output is correct |
10 |
Correct |
9 ms |
760 KB |
Output is correct |
11 |
Correct |
9 ms |
888 KB |
Output is correct |
12 |
Correct |
2 ms |
504 KB |
Output is correct |
13 |
Correct |
11 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
888 KB |
Output is correct |
2 |
Correct |
9 ms |
888 KB |
Output is correct |
3 |
Correct |
10 ms |
888 KB |
Output is correct |
4 |
Correct |
9 ms |
888 KB |
Output is correct |
5 |
Correct |
12 ms |
888 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
9 ms |
888 KB |
Output is correct |
8 |
Correct |
10 ms |
892 KB |
Output is correct |
9 |
Correct |
9 ms |
888 KB |
Output is correct |
10 |
Correct |
10 ms |
888 KB |
Output is correct |
11 |
Correct |
13 ms |
888 KB |
Output is correct |
12 |
Correct |
13 ms |
888 KB |
Output is correct |
13 |
Correct |
10 ms |
888 KB |
Output is correct |
14 |
Correct |
10 ms |
888 KB |
Output is correct |
15 |
Correct |
14 ms |
888 KB |
Output is correct |
16 |
Correct |
9 ms |
888 KB |
Output is correct |
17 |
Correct |
11 ms |
888 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
12 ms |
892 KB |
Output is correct |
20 |
Correct |
12 ms |
888 KB |
Output is correct |
21 |
Correct |
13 ms |
888 KB |
Output is correct |
22 |
Correct |
11 ms |
888 KB |
Output is correct |
23 |
Correct |
9 ms |
892 KB |
Output is correct |
24 |
Correct |
8 ms |
888 KB |
Output is correct |
25 |
Correct |
11 ms |
892 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
9 ms |
760 KB |
Output is correct |
28 |
Correct |
9 ms |
760 KB |
Output is correct |
29 |
Correct |
9 ms |
888 KB |
Output is correct |
30 |
Correct |
2 ms |
504 KB |
Output is correct |
31 |
Correct |
11 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
1528 KB |
Output is correct |
2 |
Correct |
205 ms |
2188 KB |
Output is correct |
3 |
Correct |
54 ms |
1400 KB |
Output is correct |
4 |
Correct |
70 ms |
1528 KB |
Output is correct |
5 |
Correct |
66 ms |
1532 KB |
Output is correct |
6 |
Correct |
54 ms |
1500 KB |
Output is correct |
7 |
Correct |
11 ms |
888 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
12 ms |
892 KB |
Output is correct |
10 |
Correct |
12 ms |
888 KB |
Output is correct |
11 |
Correct |
13 ms |
888 KB |
Output is correct |
12 |
Correct |
11 ms |
888 KB |
Output is correct |
13 |
Correct |
9 ms |
892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
888 KB |
Output is correct |
2 |
Correct |
9 ms |
888 KB |
Output is correct |
3 |
Correct |
10 ms |
888 KB |
Output is correct |
4 |
Correct |
9 ms |
888 KB |
Output is correct |
5 |
Correct |
12 ms |
888 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
9 ms |
888 KB |
Output is correct |
8 |
Correct |
10 ms |
892 KB |
Output is correct |
9 |
Correct |
9 ms |
888 KB |
Output is correct |
10 |
Correct |
10 ms |
888 KB |
Output is correct |
11 |
Correct |
13 ms |
888 KB |
Output is correct |
12 |
Correct |
13 ms |
888 KB |
Output is correct |
13 |
Correct |
10 ms |
888 KB |
Output is correct |
14 |
Correct |
10 ms |
888 KB |
Output is correct |
15 |
Correct |
14 ms |
888 KB |
Output is correct |
16 |
Correct |
9 ms |
888 KB |
Output is correct |
17 |
Correct |
61 ms |
1528 KB |
Output is correct |
18 |
Correct |
205 ms |
2188 KB |
Output is correct |
19 |
Correct |
54 ms |
1400 KB |
Output is correct |
20 |
Correct |
70 ms |
1528 KB |
Output is correct |
21 |
Correct |
66 ms |
1532 KB |
Output is correct |
22 |
Correct |
54 ms |
1500 KB |
Output is correct |
23 |
Correct |
11 ms |
888 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
12 ms |
892 KB |
Output is correct |
26 |
Correct |
12 ms |
888 KB |
Output is correct |
27 |
Correct |
13 ms |
888 KB |
Output is correct |
28 |
Correct |
11 ms |
888 KB |
Output is correct |
29 |
Correct |
9 ms |
892 KB |
Output is correct |
30 |
Correct |
49 ms |
1500 KB |
Output is correct |
31 |
Correct |
55 ms |
1656 KB |
Output is correct |
32 |
Correct |
106 ms |
2644 KB |
Output is correct |
33 |
Correct |
54 ms |
1528 KB |
Output is correct |
34 |
Correct |
55 ms |
1528 KB |
Output is correct |
35 |
Correct |
55 ms |
1528 KB |
Output is correct |
36 |
Correct |
226 ms |
4124 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
2 ms |
376 KB |
Output is correct |
39 |
Correct |
48 ms |
1400 KB |
Output is correct |
40 |
Correct |
58 ms |
1528 KB |
Output is correct |
41 |
Correct |
53 ms |
1516 KB |
Output is correct |
42 |
Correct |
52 ms |
1404 KB |
Output is correct |
43 |
Correct |
49 ms |
1272 KB |
Output is correct |
44 |
Correct |
2 ms |
376 KB |
Output is correct |
45 |
Correct |
17 ms |
1016 KB |
Output is correct |
46 |
Correct |
17 ms |
1012 KB |
Output is correct |
47 |
Correct |
17 ms |
1016 KB |
Output is correct |
48 |
Correct |
234 ms |
4444 KB |
Output is correct |
49 |
Correct |
231 ms |
4216 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
164 ms |
2040 KB |
Output is correct |
52 |
Correct |
50 ms |
1380 KB |
Output is correct |
53 |
Correct |
47 ms |
1344 KB |
Output is correct |
54 |
Correct |
9 ms |
888 KB |
Output is correct |
55 |
Correct |
9 ms |
760 KB |
Output is correct |
56 |
Correct |
8 ms |
888 KB |
Output is correct |
57 |
Correct |
11 ms |
892 KB |
Output is correct |
58 |
Correct |
2 ms |
376 KB |
Output is correct |
59 |
Correct |
9 ms |
760 KB |
Output is correct |
60 |
Correct |
9 ms |
760 KB |
Output is correct |
61 |
Correct |
9 ms |
888 KB |
Output is correct |
62 |
Correct |
2 ms |
504 KB |
Output is correct |
63 |
Correct |
11 ms |
888 KB |
Output is correct |