#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+500))
#define MAX ((ll)(1e16+100))
#define MOD ((ll)1e6+7)
#define mi(a,b) a=min((a),(b))
ll n,m,k;
pair<ll,ll> q[200][200];
__int128 f[200][200];
__int128 v[200][200];
int main(){
#ifdef KHOKHO
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
ios::sync_with_stdio(0);
cin>>n>>m>>k;
//cout<<n<<" "<<k<<endl;
for(int i=0; i<n; i++)
for(int j=0; j<k; j++)
cin>>q[i][j].fr>>q[i][j].sc;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
f[i][j]=f[j][i]=MAX;
for(int i=0; i<m; i++){
ll k,p,c;
cin>>k>>p>>c;
k--;
p--;
f[k][p]=c;
}
//return 0;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
for(int k=0; k<n; k++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
__int128 l=0,r=MAX;
while(l<r){
ll em=(l+r+1)>>1;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
v[i][j]=-em*f[i][j];
for(int t=0; t<k; t++){
if(q[i][t].fr>=0&&q[j][t].sc>=0)
v[i][j]=max(v[i][j],q[j][t].sc-q[i][t].fr-em*f[i][j]);
}
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
v[i][j]=max(v[i][j],v[i][k]+v[k][j]);
}
}
}
bool e=0;
for(int i=0; i<n; i++){
if(v[i][i]>=0)
e=1;
}
if(e)
l=em;
else r=em-1;
}
ll t=l;
cout<<t;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
823 ms |
1400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
1400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
522 ms |
1584 KB |
Output is correct |
2 |
Execution timed out |
1062 ms |
1584 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
1400 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |