제출 #1159775

#제출 시각아이디문제언어결과실행 시간메모리
1159775countlessTravelling Merchant (APIO17_merchant)C++20
0 / 100
46 ms2112 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 998244353; #define endl "\n" #define sp <<" "<< #define INF 1e9+21 #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) void solution() { ll n, m, k; cin >> n >> m >> k; vector<vector<pair<ll, ll>>> bs(n, vector<pair<ll, ll>>(k)); // haha bs for (ll i = 0; i < n; i++) { for (ll j = 0; j < k; j++) { cin >> bs[i][j].first >> bs[i][j].second; } } ll dist[n+5][n+5]; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { dist[i][j] = INF; } } for (ll i = 0; i < m; i++) { ll v, w, t; cin >> v >> w >> t; v--; w--; dist[v][w] = t; } // dist between any two nodes for (ll l = 0; l < n; l++) { for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]); } } } // profit between any two nodes ll profit[n+5][n+5]; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { profit[i][j] = 0; for (ll l = 0; l < k; l++) { if (bs[i][l].first == -1 || bs[j][l].second == -1) continue; profit[i][j] = max(profit[i][j], bs[j][l].second - bs[i][l].first); } } } // binary search max efficiency ll eff[n+5][n+5]; ll l = 1, r = 1e11+21; while (l < r) { ll mid = (l + r) / 2; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { eff[i][j] = min(mid * dist[i][j] - profit[i][j], (ll)INF); } } // floyd warshall again for (ll kk = 0; kk < n; kk++) { for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { eff[i][j] = min(eff[i][j], eff[i][kk] + eff[kk][j]); } } } bool flag = false; for (ll i = 0; i < n; i++) { if (eff[i][i] <= 0) { flag = true; break; } } if (flag) { l = mid + 1; } else { r = mid - 1; } } cout << r << endl; return; } signed main() { fast_io(); solution(); 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...