| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 155105 | arnold518 | Travelling Merchant (APIO17_merchant) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 100;
const int MAXM = 9900;
const int MAXK = 1000;
const ll INF = 1e12;
int N, M, K;
int B[MAXN+10][MAXK+10], S[MAXN+10][MAXK+10];
ll dist[MAXN+10][MAXN+10], adj[MAXN+10][MAXN+10], A[MAXN+10][MAXN+10];;
bool decide(ll X)
{
int i, j, k;
for(i=1; i<=N; i++) for(j=1; j<=N; j++) adj[i][j]=X*dist[i][j]-A[i][j];
/*
for(i=1; i<=N; i++)
{
for(j=1; j<=N; j++) printf("%lld ", adj[i][j]);
printf("\n");
}
printf("====================%lld\n", X);
*/
for(k=1; k<=N; k++) for(i=1; i<=N; i++) for(j=1; j<=N; j++) if(adj[i][k]!=INF && adj[k][j]!=INF) adj[i][j]=min(adj[i][k]+adj[k][j], adj[i][j]);
/*
for(i=1; i<=N; i++)
{
for(j=1; j<=N; j++) printf("%lld ", adj[i][j]);
printf("\n");
}
printf("====================!%lld\n", X);*/
for(i=1; i<=N; i++) if(adj[i][i]<0) return true;
for(i=1; i<=N; i++) for(j=1; j<=N; j++) if(i!=j && adj[i][j]+adj[j][i]<=0) return true;
return false;
}
int main()
{
int i, j, k;
scanf("%d%d%d", &N, &M, &K);
for(i=1; i<=N; i++) for(j=1; j<=K; j++) scanf("%d%d", &B[i][j], &S[i][j]);
for(i=1; i<=N; i++) for(j=1; j<=N; j++) dist[i][j]=INF;
for(i=1; i<=N; i++) dist[i][i]=0;
for(i=1; i<=M; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
dist[u][v]=w;
}
for(i=1; i<=N; i++) for(j=1; j<=N; j++)
{
if(i==j)
{
for(k=1; k<=K; k++) if(B[i][k]!=-1 && S[j][k]!=-1) A[i][j]+=max(S[j][k]-B[i][k], 0);
}
else
{
for(k=1; k<=K; k++) if(B[i][k]!=-1 && S[j][k]!=-1) A[i][j]=max(A[i][j], S[j][k]-B[i][k]);
}
}
for(k=1; k<=N; k++) for(i=1; i<=N; i++) for(j=1; j<=N; j++) if(dist[i][k]!=INF && dist[k][j]!=INF) dist[i][j]=min(dist[i][k]+dist[k][j], dist[i][j]);
ll lo=0, hi=1e15;
while(lo+1<hi)
{
ll mid=lo+hi>>1;
if(decide(mid)) lo=mid;
else hi=mid;
}
printf("%lld", lo);
}