#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
const ll N=105,K=1010,INF=LLONG_MAX/2;
ll n,m,k,lo=1,hi=1e9,mid,ans,s[N][K],b[N][K],t[N][N],p[N][N],dp[N][N];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)t[i][j]=INF;
for(int j=0;j<k;j++)cin>>b[i][j]>>s[i][j];
}
for(int i=0;i<m;i++){
ll ai,bi,ci;
cin>>ai>>bi>>ci,ai--,bi--;
t[ai][bi]=ci;
}
for(int x=0;x<n;x++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
t[i][j]=min(t[i][j],t[i][x]+t[x][j]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int x=0;x<k;x++)
if(s[j][x]!=-1 and b[i][x]!=-1)p[i][j]=max(p[i][j],s[j][x]-b[i][x]);
while(lo<=hi){
mid=(lo+hi)/2;
bool ok=0;
for(int i=0;i<n;i++)for(int j=0;j<n;j++)dp[i][j]=mid*min(t[i][j],INF/mid)-p[i][j];
for(int x=0;x<n;x++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
dp[i][j]=min(dp[i][j],dp[i][x]+dp[x][j]);
for(int i=0;i<n;i++)if(dp[i][i]<=0)ok=1;
if(ok)ans=mid,lo=mid+1;
else hi=mid-1;
}
cout<<ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |