제출 #370663

#제출 시각아이디문제언어결과실행 시간메모리
370663mihai145여행하는 상인 (APIO17_merchant)C++14
0 / 100
127 ms3156 KiB
// // Created by mihai145 on 24.02.2021. // #include <iostream> #include <vector> #include <queue> using namespace std; const int NMAX = 100; const int KMAX = 1000; const long long INF = 1e15; int N, M, K; int buy[NMAX + 2][KMAX + 2], sell[NMAX + 2][KMAX + 2]; int bestProfit[NMAX + 2][NMAX + 2]; long long minTime[NMAX + 2][NMAX + 2]; void CalcBestProfit() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i != j) { //bestProfit[i][j] = 0; for (int k = 1; k <= K; k++) { if (sell[j][k] != -1 && buy[i][k] != -1) { bestProfit[i][j] = max(bestProfit[i][j], sell[j][k] - buy[i][k]); } } } } } } void CalcMinTime() { for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (minTime[i][k] != INF && minTime[k][j] != INF) minTime[i][j] = min(minTime[i][j], minTime[i][k] + minTime[k][j]); } } } } long long mt[NMAX + 2][NMAX + 2]; bool LessThan(long long R) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (minTime[i][j] == INF) { mt[i][j] = INF; } else { mt[i][j] = bestProfit[i][j] - R * minTime[i][j]; } } } for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (mt[i][k] != INF && mt[k][j] != INF) { mt[i][j] = max(mt[i][j], mt[i][k] + mt[k][j]); } } } } for (int i = 1; i <= N; i++) { if (mt[i][i] >= 0) { return false; } } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M >> K; for (int i = 1; i <= N; i++) { for (int j = 1; j <= K; j++) { cin >> buy[i][j] >> sell[i][j]; } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { minTime[i][j] = INF; } } for (int i = 1; i <= M; i++) { int u, v, t; cin >> u >> v >> t; minTime[u][v] = t; } CalcBestProfit(); CalcMinTime(); /* cout << "BEST PROFIT\n"; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { cout << bestProfit[i][j] << " "; } cout << '\n'; } cout << "\n\n\n"; cout << "MIN TIME\n"; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { cout << minTime[i][j] << " "; } cout << '\n'; } cout << "\n\n\n"; */ long long st = 0, dr = INF, sol = 0; while (st <= dr) { long long mid = (st + dr) >> 1; if (LessThan(mid)) { dr = mid - 1; } else { sol = mid; st = mid + 1; } } cout << sol << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...