Submission #702553

#	Time	Username	Problem	Language	Result	Execution time	Memory
702553		Abrar_Al_Samit	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	96 ms	4148 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

const int nax = 101;
const long long INF = 1e18;

int n, m, k;
long long b[nax][nax*10], s[nax][nax*10];
long long graph[nax][nax], graph2[nax][nax];
long long profit[nax][nax];

void floyd_warshall(long long g[nax][nax]) {
  for(int y=1; y<=n; ++y) {
    for(int x=1; x<=n; ++x) {
      for(int z=1; z<=n; ++z) {
        g[x][z] = min(g[x][z], g[x][y]+g[y][z]);
      }
    }
  }
}
void PlayGround() {
  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) {
      graph[i][j] = INF;
    }
  }
  for(int i=0; i<m; ++i) {
    int u, v, w;
    cin>>u>>v>>w;
    graph[u][v] = w;
  }

  floyd_warshall(graph);

  for(int x=1; x<=k; ++x) {
    for(int i=1; i<=n; ++i) {
      if(b[i][x]==-1) continue;
      for(int j=1; j<=n; ++j) {
        if(s[j][x]==-1) continue;

        profit[i][j] = max(profit[i][j], s[j][x] - b[i][x]);
      }
    }
  }

  long long lo = 0, hi = INF;
  while(lo<hi) {
    long long mid = (1+lo+hi) / 2;

    for(int i=1; i<=n; ++i) {
      for(int j=1; j<=n; ++j) {
        graph2[i][j] = mid * min(graph[i][j], INF/mid) - profit[i][j];
      }
    }
    floyd_warshall(graph2);

    bool ok = false;
    for(int i=1; i<=n; ++i) if(graph2[i][i]<=0) {
      ok = true;
    }
    if(ok) lo = mid;
    else hi = mid-1;
  }

  cout<<lo<<'\n';
  //cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34