제출 #704082

#제출 시각아이디문제언어결과실행 시간메모리
704082Cyanmond여행하는 상인 (APIO17_merchant)C++17
100 / 100
81 ms2132 KiB
#include <bits/stdc++.h> using i64 = long long; constexpr int inf32 = 1 << 30; constexpr i64 inf = 1ll << 50; void calcMinDist(std::vector<std::vector<i64>> &graph) { const int n = (int)graph.size(); for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { graph[i][j] = std::min(graph[i][j], graph[i][k] + graph[k][j]); } } } } void calcMaxDist(std::vector<std::vector<i64>> &graph) { const int n = (int)graph.size(); for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { graph[i][j] = std::max(graph[i][j], graph[i][k] + graph[k][j]); graph[i][j] = std::min(graph[i][j], inf / 10); } } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, M, K; std::cin >> N >> M >> K; std::vector<std::vector<i64>> buyList(N, std::vector<i64>(K)), sellList(N, std::vector<i64>(K)); for (int i = 0; i < N; ++i) { for (int j = 0; j < K; ++j) { std::cin >> buyList[i][j] >> sellList[i][j]; } } std::vector<std::vector<i64>> baseGraph(N, std::vector<i64>(N, inf32)); for (int i = 0; i < M; ++i) { int v, w; i64 t; std::cin >> v >> w >> t; --v, --w; baseGraph[v][w] = t; } calcMinDist(baseGraph); std::vector<std::vector<i64>> profitList(N, std::vector<i64>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { i64 ma = 0; for (int k = 0; k < K; ++k) { if (buyList[i][k] == -1 or sellList[j][k] == -1) { continue; } ma = std::max(ma, sellList[j][k] - buyList[i][k]); } profitList[i][j] = ma; } } i64 ok = 0, ng = inf32; while (ng - ok > 1) { const auto mid = (ok + ng) / 2; std::vector<std::vector<i64>> realGraph(N, std::vector<i64>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { realGraph[i][j] = (profitList[i][j] - mid * baseGraph[i][j]); realGraph[i][j] = std::max(realGraph[i][j], -inf); } } for (int i = 0; i < N; ++i) { realGraph[i][i] = -inf; } calcMaxDist(realGraph); bool isOk = false; for (int i = 0; i < N; ++i) { if (realGraph[i][i] >= 0) { isOk = true; } } if (isOk) { ok = mid; } else { ng = mid; } } std::cout << ok << std::endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...