Submission #1126752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126752		holyrock	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	64 ms	2120 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mxn = 105;
const ll mxk = 1005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dist[mxn][mxn];
ll best[mxn][mxn];
ll trmp[mxn][mxn];
ll b[mxn][mxk];
ll s[mxn][mxk];
ll n, m, k;

void floyd_warshall(ll d[mxn][mxn]) {
    for (ll k = 1; k <= n; k++) {
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

bool chk(ll m) {
    memset(trmp, 0x3f, sizeof(trmp));
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            if (i != j && dist[i][j] != inf) {
                trmp[i][j] = dist[i][j] * m - best[i][j];
            }
        }
    }
    floyd_warshall(trmp);
    for (ll i = 1; i <= n; i++) {
        if (trmp[i][i] <= 0) return true;
    }
    return false;
}

int main() {
    (void)!scanf("%lld%lld%lld", &n, &m, &k);
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= k; j++) {
            (void)!scanf("%lld%lld", &b[i][j], &s[i][j]);
        }
    }

    memset(dist, 0x3f, sizeof(dist));
    for (ll i = 1; i <= m; i++) {
        ll v, w, t;
        (void)!scanf("%lld%lld%lld", &v, &w, &t);
        dist[v][w] = min(dist[v][w], t);
    }
    floyd_warshall(dist);

    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            for (ll p = 1; p <= k; p++) {
                if (b[i][p] != -1 && s[j][p] != -1)
                best[i][j] = max(best[i][j], s[j][p] - b[i][p]);
            }
        }
    }

    ll l = 0, r = 2e9;
    while (r - l > 1) {
        m = l + (r - l) / 2;
        if (chk(m)) l = m;
        else r = m;
    }
    printf("%lld\n", l);
}

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