Submission #701133

#	Time	Username	Problem	Language	Result	Execution time	Memory
701133		Abrar_Al_Samit	여행하는 상인 (APIO17_merchant)	C++17	0 / 100	18 ms	2400 KiB

merchant

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

const int INF = 1e9;
const int nax = 101;
vector<pair<int,int>>market[nax];

int g[nax][nax];
int dist[nax][nax];
void PlayGround() {
  int n, m, k;
  cin>>n>>m>>k;

  for(int i=1; i<=n; ++i) {
    for(int j=1; j<=k; ++j) {
      int b, s;
      cin>>b>>s;
      market[i].emplace_back(b, s);
    }
  }

  for(int i=1; i<=n; ++i) {
    for(int j=1; j<=n; ++j) {
      if(i!=j) dist[i][j] = INF;
    }
  }
  for(int i=0; i<m; ++i) {
    int u, v, w;
    cin>>u>>v>>w;
    g[u][v] = w;
    dist[u][v] = w;
  }


  for(int b=1; b<=n; ++b) {
    for(int a=1; a<=n; ++a) {
      for(int c=1; c<=n; ++c) {
        dist[a][c] = min(dist[a][c], dist[a][b]+dist[b][c]);
      }
    }
  }

  double ans = 0;
  for(int item=0; item<k; ++item) {
    for(int sell=2; sell<=n; ++sell) {
      double profit = market[sell][item].second - market[1][item].first;
      double d = dist[1][sell] + dist[sell][1];
      ans = max(ans, profit / d);
    }
  }
  cout<<floor(ans)<<'\n';


}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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