Submission #262658

#	Time	Username	Problem	Language	Result	Execution time	Memory
262658		casperwang	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	501 ms	2168 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];
pii 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;
      dp[i][j] = pii(0, 1);
    }
  }
  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 (dis[i][j] == INF) continue;
      dp[i][j].ss = dis[i][j];
      for (int k = 0; k < K; k++) {
        if (S[j][k] == -1 || B[i][k] == -1) continue;
        dp[i][j].ff = max(dp[i][j].ff, S[j][k] - B[i][k]);
      }
    }
  }
  for (int p = 0; p < 1e8/n/n/n; p++) {
    for (int k = 1; k <= n; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          if ((double) dp[i][j].ff / dp[i][j].ss < (double) (dp[i][k].ff + dp[k][j].ff) / (dp[i][k].ss + dp[k][j].ss)) {
            dp[i][j] = pii(dp[i][k].ff + dp[k][j].ff, dp[i][k].ss + dp[k][j].ss);
          }
        }
      }
    }
  }
  for (int i = 1; i <= n; i++)
    ans = max(ans, dp[i][i].ff / dp[i][i].ss);
  cout << ans << "\n";
}

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