#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define upd(x, y) x=min(x, y)
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=20000000000000010LL;
const int mod=1000000007;
const int MAXN=110, MAXK=1010;
ll n, m, k, u, v, x, y, t, a, b, ans;
ll G[MAXN][MAXN], val[MAXN][MAXN];
ll B[MAXN][MAXK], S[MAXN][MAXK];
ll G2[MAXN][MAXN], dist[MAXN];
inline ll _mul(ll x, ll y){
if (INF/x<y+5) return INF;
return x*y;
}
bool check(ll x){
//memset(G2, 0, sizeof(G2));
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) G2[i][j]=_mul(x, G[i][j])-val[i][j];
//cerr<<"G2:\n";for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cerr<<G2[i][j]<<" \n"[j==n];cerr<<'\n';
memset(dist, 63, sizeof(dist));
dist[1]=0;
for (int shit=1; shit<=n; shit++){
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (G[i][j]<=inf){
ll d=dist[i]+G2[i][j];
if (d<dist[j]){
dist[j]=d;
if (shit==n) return 1;
}
}
}
// pas dor manfi nadarim!
for (int x=1; x<=n; x++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) upd(G2[i][j], G2[i][x]+G2[x][j]);
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (i!=j && G[i][j]<=inf && G2[j][i]+G2[i][j]<=0) return 1;
return 0;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
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];
}
memset(G, 63, sizeof(G));
for (int i=1; i<=n; i++) G[i][i]=0;
while (m--){
cin>>u>>v>>x;
upd(G[u][v], x);
}
for (int x=1; x<=n; x++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) upd(G[i][j], G[i][x]+G[x][j]);
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) for (int x=1; x<=k; x++)
if (B[i][x]!=-1 && S[j][x]!=-1) val[i][j]=max(val[i][j], S[j][x]-B[i][x]);
//cerr<<"val:\n";for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cerr<<val[i][j]<<" \n"[j==n];cerr<<'\n';
/*
debug(check(2))
return 0;
*/
int dwn=0, up=inf;
while (up-dwn>1){
int mid=(dwn+up)>>1;
if (check(mid)) dwn=mid;
else up=mid;
}
cout<<dwn<<'\n';
return 0;
}
/*
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
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
2176 KB |
Output is correct |
2 |
Correct |
75 ms |
1380 KB |
Output is correct |
3 |
Correct |
61 ms |
1280 KB |
Output is correct |
4 |
Correct |
14 ms |
896 KB |
Output is correct |
5 |
Correct |
13 ms |
896 KB |
Output is correct |
6 |
Correct |
13 ms |
896 KB |
Output is correct |
7 |
Correct |
14 ms |
896 KB |
Output is correct |
8 |
Correct |
5 ms |
512 KB |
Output is correct |
9 |
Correct |
13 ms |
1024 KB |
Output is correct |
10 |
Correct |
13 ms |
896 KB |
Output is correct |
11 |
Correct |
13 ms |
896 KB |
Output is correct |
12 |
Correct |
5 ms |
512 KB |
Output is correct |
13 |
Correct |
15 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
896 KB |
Output is correct |
2 |
Correct |
13 ms |
896 KB |
Output is correct |
3 |
Correct |
14 ms |
896 KB |
Output is correct |
4 |
Correct |
13 ms |
1024 KB |
Output is correct |
5 |
Correct |
14 ms |
896 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
14 ms |
1024 KB |
Output is correct |
8 |
Correct |
14 ms |
1024 KB |
Output is correct |
9 |
Correct |
13 ms |
1024 KB |
Output is correct |
10 |
Correct |
13 ms |
896 KB |
Output is correct |
11 |
Correct |
13 ms |
1024 KB |
Output is correct |
12 |
Correct |
13 ms |
1024 KB |
Output is correct |
13 |
Correct |
13 ms |
896 KB |
Output is correct |
14 |
Correct |
13 ms |
1024 KB |
Output is correct |
15 |
Correct |
14 ms |
1024 KB |
Output is correct |
16 |
Correct |
13 ms |
896 KB |
Output is correct |
17 |
Correct |
14 ms |
1024 KB |
Output is correct |
18 |
Correct |
4 ms |
512 KB |
Output is correct |
19 |
Correct |
12 ms |
896 KB |
Output is correct |
20 |
Correct |
13 ms |
896 KB |
Output is correct |
21 |
Correct |
14 ms |
1024 KB |
Output is correct |
22 |
Correct |
13 ms |
896 KB |
Output is correct |
23 |
Correct |
12 ms |
896 KB |
Output is correct |
24 |
Correct |
13 ms |
896 KB |
Output is correct |
25 |
Correct |
14 ms |
896 KB |
Output is correct |
26 |
Correct |
5 ms |
512 KB |
Output is correct |
27 |
Correct |
13 ms |
1024 KB |
Output is correct |
28 |
Correct |
13 ms |
896 KB |
Output is correct |
29 |
Correct |
13 ms |
896 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
15 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
1536 KB |
Output is correct |
2 |
Correct |
124 ms |
2168 KB |
Output is correct |
3 |
Correct |
64 ms |
1536 KB |
Output is correct |
4 |
Correct |
78 ms |
1536 KB |
Output is correct |
5 |
Correct |
55 ms |
1536 KB |
Output is correct |
6 |
Correct |
66 ms |
1536 KB |
Output is correct |
7 |
Correct |
14 ms |
1024 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
12 ms |
896 KB |
Output is correct |
10 |
Correct |
13 ms |
896 KB |
Output is correct |
11 |
Correct |
14 ms |
1024 KB |
Output is correct |
12 |
Correct |
13 ms |
896 KB |
Output is correct |
13 |
Correct |
12 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
896 KB |
Output is correct |
2 |
Correct |
13 ms |
896 KB |
Output is correct |
3 |
Correct |
14 ms |
896 KB |
Output is correct |
4 |
Correct |
13 ms |
1024 KB |
Output is correct |
5 |
Correct |
14 ms |
896 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
14 ms |
1024 KB |
Output is correct |
8 |
Correct |
14 ms |
1024 KB |
Output is correct |
9 |
Correct |
13 ms |
1024 KB |
Output is correct |
10 |
Correct |
13 ms |
896 KB |
Output is correct |
11 |
Correct |
13 ms |
1024 KB |
Output is correct |
12 |
Correct |
13 ms |
1024 KB |
Output is correct |
13 |
Correct |
13 ms |
896 KB |
Output is correct |
14 |
Correct |
13 ms |
1024 KB |
Output is correct |
15 |
Correct |
14 ms |
1024 KB |
Output is correct |
16 |
Correct |
13 ms |
896 KB |
Output is correct |
17 |
Correct |
73 ms |
1536 KB |
Output is correct |
18 |
Correct |
124 ms |
2168 KB |
Output is correct |
19 |
Correct |
64 ms |
1536 KB |
Output is correct |
20 |
Correct |
78 ms |
1536 KB |
Output is correct |
21 |
Correct |
55 ms |
1536 KB |
Output is correct |
22 |
Correct |
66 ms |
1536 KB |
Output is correct |
23 |
Correct |
14 ms |
1024 KB |
Output is correct |
24 |
Correct |
4 ms |
512 KB |
Output is correct |
25 |
Correct |
12 ms |
896 KB |
Output is correct |
26 |
Correct |
13 ms |
896 KB |
Output is correct |
27 |
Correct |
14 ms |
1024 KB |
Output is correct |
28 |
Correct |
13 ms |
896 KB |
Output is correct |
29 |
Correct |
12 ms |
896 KB |
Output is correct |
30 |
Correct |
73 ms |
1656 KB |
Output is correct |
31 |
Correct |
74 ms |
1664 KB |
Output is correct |
32 |
Correct |
87 ms |
2688 KB |
Output is correct |
33 |
Correct |
72 ms |
1664 KB |
Output is correct |
34 |
Correct |
75 ms |
1664 KB |
Output is correct |
35 |
Correct |
73 ms |
1664 KB |
Output is correct |
36 |
Correct |
134 ms |
4192 KB |
Output is correct |
37 |
Correct |
5 ms |
512 KB |
Output is correct |
38 |
Correct |
5 ms |
512 KB |
Output is correct |
39 |
Correct |
68 ms |
1408 KB |
Output is correct |
40 |
Correct |
78 ms |
1536 KB |
Output is correct |
41 |
Correct |
74 ms |
1536 KB |
Output is correct |
42 |
Correct |
70 ms |
1408 KB |
Output is correct |
43 |
Correct |
67 ms |
1408 KB |
Output is correct |
44 |
Correct |
5 ms |
512 KB |
Output is correct |
45 |
Correct |
15 ms |
1024 KB |
Output is correct |
46 |
Correct |
16 ms |
1024 KB |
Output is correct |
47 |
Correct |
15 ms |
1024 KB |
Output is correct |
48 |
Correct |
136 ms |
4472 KB |
Output is correct |
49 |
Correct |
133 ms |
4216 KB |
Output is correct |
50 |
Correct |
5 ms |
512 KB |
Output is correct |
51 |
Correct |
106 ms |
2176 KB |
Output is correct |
52 |
Correct |
75 ms |
1380 KB |
Output is correct |
53 |
Correct |
61 ms |
1280 KB |
Output is correct |
54 |
Correct |
14 ms |
896 KB |
Output is correct |
55 |
Correct |
13 ms |
896 KB |
Output is correct |
56 |
Correct |
13 ms |
896 KB |
Output is correct |
57 |
Correct |
14 ms |
896 KB |
Output is correct |
58 |
Correct |
5 ms |
512 KB |
Output is correct |
59 |
Correct |
13 ms |
1024 KB |
Output is correct |
60 |
Correct |
13 ms |
896 KB |
Output is correct |
61 |
Correct |
13 ms |
896 KB |
Output is correct |
62 |
Correct |
5 ms |
512 KB |
Output is correct |
63 |
Correct |
15 ms |
896 KB |
Output is correct |