제출 #704073

#제출 시각아이디문제언어결과실행 시간메모리
704073Forested여행하는 상인 (APIO17_merchant)C++17
100 / 100
116 ms4408 KiB
#include <bits/stdc++.h> using namespace std; using i32 = int; using i64 = long long; template <typename T> using Vec = vector<T>; #define OVERRIDE4(a, b, c, d, ...) d #define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i) #define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i) #define REP(...) OVERRIDE4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__) #define PER2(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i) #define PER3(i, m, n) for (i32 i = (i32)(n) - 1; i >= (i32)(m); --i) #define PER(...) OVERRIDE4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__) #define ALL(x) begin(x), end(x) constexpr i32 INF = 1001001001; constexpr i64 INF64 = 3003003003003003003LL; template <typename T> bool chmin(T &x, const T &y) { if (x > y) { x = y; return true; } else { return false; } } template <typename T> bool chmax(T &x, const T &y) { if (x < y) { x = y; return true; } else { return false; } } bool has_cycle(i32 n, Vec<Vec<i32>> g) { Vec<i32> deg(n); REP(i, n) for (i32 j : g[i]) { ++deg[j]; } queue<i32> que; REP(i, n) { if (deg[i] == 0) { que.push(i); } } while (!que.empty()) { i32 v = que.front(); que.pop(); for (i32 u : g[v]) { if (--deg[u] == 0) { que.push(u); } } } return count(ALL(deg), 0) != n; } int main() { i32 n, m, k; cin >> n >> m >> k; Vec<Vec<i64>> b(n, Vec<i64>(k)), s(n, Vec<i64>(k)); REP(i, n) { REP(j, k) { cin >> b[i][j] >> s[i][j]; } } Vec<Vec<pair<i32, i64>>> g(n); REP(i, m) { i32 u, v, t; cin >> u >> v >> t; --u; --v; g[u].emplace_back(v, t); } Vec<Vec<i64>> dist(n, Vec<i64>(n, INF64)); REP(i, n) { dist[i][i] = 0; for (auto [j, t] : g[i]) { dist[i][j] = t; } } REP(k, n) REP(i, n) REP(j, n) { chmin(dist[i][j], dist[i][k] + dist[k][j]); } Vec<Vec<i64>> profit(n, Vec<i64>(n, 0)); REP(i, n) REP(j, n) REP(l, k) { if (b[i][l] != -1 && s[j][l] != -1) { chmax(profit[i][j], s[j][l] - b[i][l]); } } const auto judge = [&](i64 x) -> bool { Vec<Vec<i64>> e(n, Vec<i64>(n, INF64)); REP(i, n) REP(j, n) { if (dist[i][j] != INF64) { e[i][j] = x * dist[i][j] - profit[i][j]; } } Vec<i64> d(n, 0); REP(iter, n) REP(i, n) REP(j, n) { if (chmin(d[j], d[i] + e[i][j]) && iter == n - 1) { return true; } } Vec<Vec<i32>> g_(n); REP(i, n) REP(j, n) { if (i != j && d[i] + e[i][j] == d[j]) { g_[i].push_back(j); } } return has_cycle(n, g_); }; i64 ok = 0, ng = 2LL * INF; while (ng - ok > 1) { i64 mid = (ok + ng) / 2; if (judge(mid)) { ok = mid; } else { ng = mid; } } cout << ok << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...