제출 #820841

#제출 시각아이디문제언어결과실행 시간메모리
820841Alihan_8여행하는 상인 (APIO17_merchant)C++17
100 / 100
100 ms4188 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define pb push_back #define ln '\n' #define int long long template <class _T> bool chmin(_T &x, const _T &y){ bool flag = false; if ( x > y ){ x = y; flag |= true; } return flag; } template <class _T> bool chmax(_T &x, const _T &y){ bool flag = false; if ( x < y ){ x = y; flag |= true; } return flag; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; vector <vector<int>> B(n, vector <int> (k)), S(n, vector <int> (k)); for ( int i = 0; i < n; i++ ){ for ( int j = 0; j < k; j++ ){ cin >> B[i][j] >> S[i][j]; } } const int inf = 1e9 + 501; vector <vector<int>> dis(n, vector <int> (n, inf)); for ( int i = 0; i < m; i++ ){ int u, v, t; cin >> u >> v >> t; dis[--u][--v] = t; } auto RunFloyd = [&](auto &d){ for ( int i = 0; i < n; i++ ){ for ( int j = 0; j < n; j++ ){ for ( int k = 0; k < n; k++ ){ chmin(d[j][k], d[j][i] + d[i][k]); } } } }; RunFloyd(dis); vector <vector<int>> P(n, vector <int> (n)); for ( int i = 0; i < n; i++ ){ for ( int j = 0; j < n; j++ ){ for ( int _k = 0; _k < k; _k++ ){ if ( B[i][_k] == -1 or S[j][_k] == -1 ){ continue; } chmax(P[i][j], -B[i][_k] + S[j][_k]); } } } auto ok = [&](int M){ auto a = P; for ( int i = 0; i < n; i++ ){ for ( int j = 0; j < n; j++ ){ a[i][j] = M * dis[i][j] - P[i][j]; } } RunFloyd(a); bool flag = false; for ( int i = 0; i < n; i++ ){ flag |= (a[i][i] <= 0); } return flag; }; int l = 0, r = 1e9 + 1; while ( l + 1 < r ){ int md = (l + r) >> 1; if ( ok(md) ) l = md; else r = md; } cout << l; cout << '\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...