제출 #747167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747167		c2zi6	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	134 ms	3016 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
using ld = long double;
using ll = long long;

int n;
vector<vector<int>> cst, prf;

//can answer be more than ans
bool can(ll ans) {
    vector<vector<ll>> gp(n, vector<ll>(n));
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            gp[u][v] = prf[u][v] - cst[u][v] * ans;
        }
    }
    for (int k = 0; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                gp[u][v] = max(gp[u][v], gp[u][k] + gp[k][v]);
            }
        }
    }

    ll mx = -1e18;
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            if (u == v) continue;
            mx = max(mx, gp[u][v] + gp[v][u]);
        }
    }
    return mx >= 0;
}

void solve() {
    int m, k;
    cin >> n >> m >> k;
    vector<vector<int>> b(n), s(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            int x, y;
            cin >> x >> y;
            b[i].push_back(x);
            s[i].push_back(y);
        }
    }
    cst = vector<vector<int>>(n, vector<int>(n, 1e9));
    for (int i = 0; i < m; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        u--, v--;
        cst[u][v] = t;
    }
    for (int u = 0; u < n; u++) cst[u][u] = 0;
    for (int k = 0; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                cst[u][v] = min(cst[u][v], cst[u][k] + cst[k][v]);
            }
        }
    }
    prf = vector<vector<int>>(n, vector<int>(n, 0));
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            for (int i = 0; i < k; i++) {
                if (s[v][i] == -1 || b[u][i] == -1) continue;
                prf[u][v] = max(prf[u][v], s[v][i] - b[u][i]);
            }
        }
    }
    ll l = -1, r = 1e12;
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        if (can(m)) l = m;
        else r = m;
    }
    cout << l << endl;
}

int main() {
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34