#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)(1e9+100))
#define MOD ((ll)1e6+7)
#define mi(a,b) a=min((a),(b))
ll n,m,k;
pair<ll,ll> q[2000][2000];
ll f[2000][2000];
ll v[2000][2000];
ll ve[2000][2000];
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 k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
//v[i][j]=-em*f[i][j];
ve[i][j]=0;
for(int t=0; t<k; t++){
if(q[i][t].fr>=0&&q[j][t].sc>=0)
ve[i][j]=max(v[i][j],q[j][t].sc-q[i][t].fr);
}
}
}
ll l=0,r=MAX;
while(l<r){
ll em=(l+r+1)>>1ll;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
v[i][j]=ve[i][j]-em*f[i][j];
for(int k=0; k<n; k++){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
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;
}
cout<<l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
3704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
