| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1054070 | 2024-08-12T05:49:15 Z | ㅇ(#11107) | Land of the Rainbow Gold (APIO17_rainbow) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using ll=long long;
using pii=array<int,2>;
const ll inf=1e9;
const int N=105,M=1005;
int n,m,k;
ll b[N][M],s[N][M];
ll g[N][N],c[N][N],d[N][N];
bool ok(ll C){
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=C*g[i][j]-c[i][j];
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int i=1;i<=n;i++) if(d[i][i]<=0) return true;
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
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++) g[i][j]=inf;
for(int u,v,w,i=1;i<=m;i++){
cin>>u>>v>>w;
g[u][v]=w;
}
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
for(int t=1;t<=k;t++) if(b[i][t]!=-1&&s[j][t]!=-1) c[i][j]=max(c[i][j],s[j][t]-b[i][t]);
}
ll L=1,R=1e9;
while(L<=R){
int M=(L+R)>>1;
if(ok(M)) L=M+1;
else R=M-1;
}
cout<<L-1;
return 0;
}