Submission #262689

#	Time	Username	Problem	Language	Result	Execution time	Memory
262689		casperwang	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	192 ms	2424 KiB

merchant

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
 
const int MAXN = 100;
const int MAXK = 1000;
const int INF = 1e18;
int n, m, K;
int ans;
int B[MAXN+1][MAXK];
int S[MAXN+1][MAXK];
int a, b, c;
int dis[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1];
 
signed main() {
  cin >> n >> m >> K;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < K; j++) {
      cin >> B[i][j] >> S[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      dis[i][j] = INF;
    }
  }
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    dis[a][b] = c; 
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    } 
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j || dis[i][j] == INF) continue;
      for (int k = 0; k < K; k++) {
        if (S[j][k] == -1 || B[i][k] == -1) continue;
        dp[i][j] = max(dp[i][j], S[j][k] - B[i][k]);
      }
    }
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (dp[i][j] < dp[i][k] + dp[k][j] && dis[i][j] == dis[i][k] + dis[k][j]) {
          dp[i][j] = dp[i][k] + dp[k][j];
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j || dis[i][j] == INF || dis[j][i] == INF) continue;
      ans = max(ans, (dp[i][j] + dp[j][i]) / (dis[i][j] + dis[j][i]));
    }
  }
  cout << ans << "\n";
}

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