Submission #1159757

#TimeUsernameProblemLanguageResultExecution timeMemory
1159757countlessTravelling Merchant (APIO17_merchant)C++20
0 / 100
57 ms3304 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<long long> vll; typedef vector<vector<long long>> vvll; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef set<int> si; typedef set<long long> sll; const ll MOD = 998244353; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define forn(i, n) for(ll i = 0; i < n; i++) #define rforn(i, n) for(ll i = n; i >= 0; i--) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define INF 1e9+21 #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) const int MAXN = 1005; ll dist[MAXN][MAXN], profit[MAXN][MAXN], eff[MAXN][MAXN]; 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 (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { cin >> bs[i][j].first >> bs[i][j].second; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = INF; } } for (int i = 0; i < m; i++) { int v, w, t; cin >> v >> w >> t; v--; w--; dist[v][w] = t; } // dist between any two nodes for (int l = 0; l < n; l++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = min(dist[i][j], dist[i][l] + dist[l][j]); } } } // profit between any two nodes for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { profit[i][j] = 0; for (int 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 l = 0, r = 1e11+21; while (l < r) { ll mid = (l + r) / 2; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // eff[i][j] = min(mid * dist[i][j] - profit[i][j], (ll)INF); eff[i][j] = mid * min(dist[i][j], (ll)INF / mid) - profit[i][j]; } } // floyd warshall again for (int kk = 0; kk < n; kk++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { eff[i][j] = min(eff[i][j], eff[i][kk] + eff[kk][j]); } } } // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // cout << eff[i][j] << " "; // } // cout << endl; // } // cerr << l sp r sp mid << endl; bool flag = false; for (int i = 0; i < n; i++) { if (eff[i][i] <= 0) { flag = true; break; } } if (flag) { l = mid + 1; } else { r = mid; } } cout << r - 1 << 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...