Submission #850946

#	Time	Username	Problem	Language	Result	Execution time	Memory
850946		hngwlog	Travelling Merchant (APIO17_merchant)	C++14	54 / 100	126 ms	2136 KiB

merchant

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

#define int long long
#define fi first
#define se second
#define _size(x) (int)x.size()
#define BIT(i, x) ((x >> i) & 1)
#define MASK(n) ((1 << n) - 1)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--)
#define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i)
#define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i)
#define FORALL(i, a) for (auto i: a)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

const int inf = 1e9 + 7;
const double EPS = 1e-2;

int n, m, k;
vector<vector<int>> b, s, minD, maxC;
vector<vector<pair<int, int>>> adj;

void load_minDist() {

    FOR(i, 1, n) minD[i][i] = 0;
    FOR(u, 1, n) FORALL(e, adj[u]) minD[u][e.fi] = min(minD[u][e.fi], e.se);
    FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n) minD[i][j] = min(minD[i][j], minD[i][k] + minD[k][j]);
}

void load_maxCost() {

    FOR(i, 1, n) {
        FOR(j, 1, n) {
            FOR(z, 1, k) {
                if (b[i][z] == - 1 || s[j][z] == - 1) continue;
                maxC[i][j] = max(maxC[i][j], s[j][z] - b[i][z]);
            }
        }
    }
}

bool check(double x) {

    vector<double> f(n + 1);
    FOR(t, 1, n) {
        FOR(u, 1, n) FOR(v, 1, n) {
            if (minD[u][v] == inf) continue;
            if (f[v] > f[u] + (double)x * minD[u][v] - maxC[u][v]) f[v] = f[u] + (double)x * minD[u][v] - maxC[u][v];
        }
    }
    REP(t, n) {
        FOR(u, 1, n) FOR(v, 1, n) {
            if (minD[u][v] == inf) continue;
            if (f[v] && f[v] > f[u] + (double)x * minD[u][v] - maxC[u][v]) return true;
        }
    }
    return false;
}

int32_t main() {
    fastio;

    cin >> n >> m >> k;
    b.assign(n + 1, vector<int>(k + 1));
    s.assign(n + 1, vector<int>(k + 1));
    FOR(i, 1, n) FOR(j, 1, k) cin >> b[i][j] >> s[i][j];
    adj.resize(n + 1);
    REP(i, m) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    minD.assign(n + 1, vector<int>(n + 1, inf));
    load_minDist();
    maxC.assign(n + 1, vector<int>(n + 1));
    load_maxCost();
    double l = 0;
    double r = inf;
    while (l + EPS <= r) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(l + EPS * 2) << '\n';
    return 0;
}

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