제출 #887822

#제출 시각아이디문제언어결과실행 시간메모리
887822Shayan86여행하는 상인 (APIO17_merchant)C++14
100 / 100
67 ms4624 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define Mp make_pair #define sep ' ' #define endl '\n' #define F first #define S second #define pb push_back #define all(x) (x).begin(),(x).end() #define kill(res) cout << res << '\n', exit(0); #define set_dec(x) cout << fixed << setprecision(x); #define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 107; const ll K = 1007; const ll inf = 1e9 + 7; ll n, m, k, b[N][K], s[N][K], dist[N][N], prof[N][N], res[N][N]; vector<pll> adj[N]; void floyd(){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) dist[i][j] = (i == j ? 0 : inf); for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) dist[i][j] = w; for(int kk = 1; kk <= n; kk++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ dist[i][j] = min(dist[i][j], dist[i][kk] + dist[kk][j]); } } } } void floyd2(){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) res[i][j] = inf; for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) res[i][j] = w; for(int kk = 1; kk <= n; kk++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ res[i][j] = min(res[i][j], res[i][kk] + res[kk][j]); } } } } bool check(ll mid){ for(int i = 1; i <= n; i++) adj[i].clear(); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i != j) adj[i].pb({j, (inf / dist[i][j] < mid ? 1e18 : mid * dist[i][j] - prof[i][j])}); } } floyd2(); ll mn = 1; for(int i = 1; i <= n; i++) mn = min(mn, res[i][i]); return (mn <= 0); } int main(){ fast_io; cin >> n >> m >> k; for(int i = 1; i <= n; i++){ for(int j = 1; j <= k; j++){ cin >> b[i][j] >> s[i][j]; } } int u, v, w; for(int i = 1; i <= m; i++){ cin >> u >> v >> w; adj[u].pb({v, w}); } floyd(); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ for(int kk = 1; kk <= k; kk++){ if(min(s[j][kk], b[i][kk]) != -1) prof[i][j] = max(prof[i][j], s[j][kk] - b[i][kk]); } } } ll l = 0, r = inf; while(r-l > 1){ ll mid = (l+r)/2; if(check(mid)) l = mid; else r = mid; } cout << l; }

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'void floyd()':
merchant.cpp:36:42: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) dist[i][j] = w;
      |                                          ^
merchant.cpp: In function 'void floyd2()':
merchant.cpp:49:42: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(int i = 1; i <= n; i++) for(auto [j, w]: adj[i]) res[i][j] = w;
      |                                          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...