제출 #970632

#제출 시각아이디문제언어결과실행 시간메모리
970632MinaRagy06여행하는 상인 (APIO17_merchant)C++17
100 / 100
240 ms4444 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 105, K = 1005; const ll inf = 1e18; array<ll, 2> a[N][K]; ll dist[N][N], dist2[N][N], dist3[N][N], c[N][N]; int n, m, t; bool check(ll v) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist2[i][j] = -1e18; for (int k = 1; k <= n; k++) { if (dist[i][k] + dist3[k][j] <= inf / v) { // if (i == 1 && j == 1) { // cout << -(dist[i][k] + dist3[k][j]) * v + c[k][j] << ' ' << k << ' ' << c[k][j] << ' ' << dist[i][k] << ' ' << dist3[k][j] << '\n'; // } dist2[i][j] = max(dist2[i][j], -(dist[i][k] + dist3[k][j]) * v + c[k][j]); } } } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist2[i][j] = max(dist2[i][j], dist2[i][k] + dist2[k][j]); } } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (dist2[i][k] + dist2[k][j] > dist2[i][j]) { dist2[i][j] = 1e18; } } } } // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= n; j++) { // cout << dist2[i][j] << ' '; // } // cout << '\n'; // } // cout << dist[1][2] << ' ' << dist[3][1] << ' ' << dist2[2][3] << '\n'; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) { if (dist[i][j] + dist[k][i] <= inf / v) { if (dist2[j][k] - (dist[i][j] + dist[k][i]) * v >= 0) { // cout << i << ' ' << j << ' ' << k << ' ' << i << ": " << dist2[j][k] << ' ' << dist[i][j] << ' ' << dist[k][i] << '\n'; return 1; } } } } } return 0; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> n >> m >> t; for (int i = 1; i <= n; i++) { for (int j = 0; j < t; j++) { cin >> a[i][j][0] >> a[i][j][1]; if (a[i][j][0] == -1) { a[i][j][0] = 1e18; } if (a[i][j][1] == -1) { a[i][j][1] = -1e18; } } } memset(dist, '?', sizeof dist); memset(dist3, '?', sizeof dist3); for (int i = 0, u, v, w; i < m; i++) { cin >> u >> v >> w; dist[u][v] = w; dist3[u][v] = w; } for (int i = 1; i <= n; i++) { dist[i][i] = 0; } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); dist3[i][j] = min(dist3[i][j], dist3[i][k] + dist3[k][j]); } } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { c[i][j] = -1e18; // buy at i, sell at j for (int k = 0; k < t; k++) { // if (i == 4 && j == 1) { // cout << - a[i][k][0] + a[j][k][1] << '\n'; // } c[i][j] = max(c[i][j], - a[i][k][0] + a[j][k][1]); } } } ll l = 1, r = 1e18; while (l <= r) { ll md = ((l + r) >> 1); if (check(md)) { l = md + 1; } else { r = md - 1; } } cout << r << '\n'; 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...