#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
const int lmt=1e3+10,lmt2=1e2+10;
const ll inf=2e9;
ll n,m,k;
ll b[lmt2][lmt],s[lmt2][lmt],dis[lmt2][lmt2],ok[lmt2][lmt2],lob[lmt2][lmt2];
int main(){
fastio;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++) cin>>b[i][j]>>s[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) dis[i][j]=inf;
}
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
dis[u][v]=w;
}
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>dis[i][l]+dis[l][j]){
dis[i][j]=dis[i][l]+dis[l][j];
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>=inf){
lob[i][j]=-inf;
continue;
}
for(int item=1;item<=k;item++){
if(s[j][item]==-1 || b[i][item]==-1) continue;
lob[i][j]=max(lob[i][j],s[j][item]-b[i][item]);
}
}
}
ll lo=0,hi=inf;
while(lo<hi){
ll mid=(lo+hi+1)/2;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]>=inf) ok[i][j]=-inf;
else ok[i][j]=lob[i][j]-mid*dis[i][j];
}
}
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][l]>=inf || dis[j][l]>=inf) continue;
ok[i][j]=max(ok[i][j],ok[i][l]+ok[l][j]);
}
}
}
bool on=0;
for(int i=1;i<=n;i++){
if(ok[i][i]>=0){
on=1;
break;
}
}
if(on) lo=mid;
else hi=mid-1;
}
cout<<lo<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
2060 KB |
Output is correct |
2 |
Correct |
48 ms |
1228 KB |
Output is correct |
3 |
Correct |
50 ms |
1228 KB |
Output is correct |
4 |
Correct |
8 ms |
716 KB |
Output is correct |
5 |
Correct |
8 ms |
812 KB |
Output is correct |
6 |
Correct |
7 ms |
716 KB |
Output is correct |
7 |
Correct |
11 ms |
844 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
8 ms |
808 KB |
Output is correct |
10 |
Correct |
9 ms |
716 KB |
Output is correct |
11 |
Correct |
8 ms |
816 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
7 ms |
912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
716 KB |
Output is correct |
2 |
Correct |
11 ms |
844 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
8 ms |
808 KB |
Output is correct |
5 |
Correct |
9 ms |
716 KB |
Output is correct |
6 |
Correct |
8 ms |
816 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
7 ms |
912 KB |
Output is correct |
9 |
Correct |
10 ms |
844 KB |
Output is correct |
10 |
Correct |
8 ms |
856 KB |
Output is correct |
11 |
Correct |
8 ms |
920 KB |
Output is correct |
12 |
Correct |
7 ms |
880 KB |
Output is correct |
13 |
Correct |
9 ms |
840 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
7 ms |
868 KB |
Output is correct |
16 |
Correct |
7 ms |
936 KB |
Output is correct |
17 |
Correct |
7 ms |
844 KB |
Output is correct |
18 |
Correct |
7 ms |
844 KB |
Output is correct |
19 |
Correct |
9 ms |
844 KB |
Output is correct |
20 |
Correct |
8 ms |
920 KB |
Output is correct |
21 |
Correct |
8 ms |
844 KB |
Output is correct |
22 |
Correct |
8 ms |
844 KB |
Output is correct |
23 |
Correct |
9 ms |
840 KB |
Output is correct |
24 |
Correct |
8 ms |
828 KB |
Output is correct |
25 |
Correct |
9 ms |
840 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
9 ms |
844 KB |
Output is correct |
28 |
Correct |
9 ms |
844 KB |
Output is correct |
29 |
Correct |
8 ms |
964 KB |
Output is correct |
30 |
Correct |
8 ms |
848 KB |
Output is correct |
31 |
Correct |
7 ms |
860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
840 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
9 ms |
844 KB |
Output is correct |
4 |
Correct |
9 ms |
844 KB |
Output is correct |
5 |
Correct |
8 ms |
964 KB |
Output is correct |
6 |
Correct |
8 ms |
848 KB |
Output is correct |
7 |
Correct |
7 ms |
860 KB |
Output is correct |
8 |
Correct |
55 ms |
1484 KB |
Output is correct |
9 |
Correct |
106 ms |
2116 KB |
Output is correct |
10 |
Correct |
53 ms |
1356 KB |
Output is correct |
11 |
Correct |
57 ms |
1484 KB |
Output is correct |
12 |
Correct |
56 ms |
1500 KB |
Output is correct |
13 |
Correct |
55 ms |
1484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
844 KB |
Output is correct |
2 |
Correct |
8 ms |
856 KB |
Output is correct |
3 |
Correct |
8 ms |
920 KB |
Output is correct |
4 |
Correct |
7 ms |
880 KB |
Output is correct |
5 |
Correct |
9 ms |
840 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
7 ms |
868 KB |
Output is correct |
8 |
Correct |
7 ms |
936 KB |
Output is correct |
9 |
Correct |
7 ms |
844 KB |
Output is correct |
10 |
Correct |
7 ms |
844 KB |
Output is correct |
11 |
Correct |
9 ms |
844 KB |
Output is correct |
12 |
Correct |
8 ms |
920 KB |
Output is correct |
13 |
Correct |
8 ms |
844 KB |
Output is correct |
14 |
Correct |
8 ms |
844 KB |
Output is correct |
15 |
Correct |
9 ms |
840 KB |
Output is correct |
16 |
Correct |
8 ms |
828 KB |
Output is correct |
17 |
Correct |
55 ms |
1484 KB |
Output is correct |
18 |
Correct |
106 ms |
2116 KB |
Output is correct |
19 |
Correct |
53 ms |
1356 KB |
Output is correct |
20 |
Correct |
57 ms |
1484 KB |
Output is correct |
21 |
Correct |
56 ms |
1500 KB |
Output is correct |
22 |
Correct |
55 ms |
1484 KB |
Output is correct |
23 |
Correct |
9 ms |
840 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
9 ms |
844 KB |
Output is correct |
26 |
Correct |
9 ms |
844 KB |
Output is correct |
27 |
Correct |
8 ms |
964 KB |
Output is correct |
28 |
Correct |
8 ms |
848 KB |
Output is correct |
29 |
Correct |
7 ms |
860 KB |
Output is correct |
30 |
Correct |
81 ms |
2060 KB |
Output is correct |
31 |
Correct |
48 ms |
1228 KB |
Output is correct |
32 |
Correct |
50 ms |
1228 KB |
Output is correct |
33 |
Correct |
8 ms |
716 KB |
Output is correct |
34 |
Correct |
8 ms |
812 KB |
Output is correct |
35 |
Correct |
7 ms |
716 KB |
Output is correct |
36 |
Correct |
11 ms |
844 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
8 ms |
808 KB |
Output is correct |
39 |
Correct |
9 ms |
716 KB |
Output is correct |
40 |
Correct |
8 ms |
816 KB |
Output is correct |
41 |
Correct |
1 ms |
332 KB |
Output is correct |
42 |
Correct |
7 ms |
912 KB |
Output is correct |
43 |
Correct |
51 ms |
1408 KB |
Output is correct |
44 |
Correct |
53 ms |
1612 KB |
Output is correct |
45 |
Correct |
75 ms |
2628 KB |
Output is correct |
46 |
Correct |
54 ms |
1612 KB |
Output is correct |
47 |
Correct |
58 ms |
1616 KB |
Output is correct |
48 |
Correct |
53 ms |
1612 KB |
Output is correct |
49 |
Correct |
112 ms |
4076 KB |
Output is correct |
50 |
Correct |
1 ms |
332 KB |
Output is correct |
51 |
Correct |
1 ms |
332 KB |
Output is correct |
52 |
Correct |
51 ms |
1356 KB |
Output is correct |
53 |
Correct |
53 ms |
1488 KB |
Output is correct |
54 |
Correct |
44 ms |
1484 KB |
Output is correct |
55 |
Correct |
49 ms |
1476 KB |
Output is correct |
56 |
Correct |
51 ms |
1356 KB |
Output is correct |
57 |
Correct |
1 ms |
332 KB |
Output is correct |
58 |
Correct |
9 ms |
968 KB |
Output is correct |
59 |
Correct |
11 ms |
972 KB |
Output is correct |
60 |
Correct |
8 ms |
992 KB |
Output is correct |
61 |
Correct |
118 ms |
4164 KB |
Output is correct |
62 |
Correct |
117 ms |
4156 KB |
Output is correct |
63 |
Correct |
1 ms |
332 KB |
Output is correct |