Submission #1116697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116697		OI_Account	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	93 ms	4684 KiB

merchant

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

typedef long long ll;

const int N = 100;
const int K = 1000;
const ll INF = 1'000'000'000'000'000'000;
const ll INF9 = 1'000'000'000;

int n, m, k;
ll b[N + 10][K + 10], s[N + 10][K + 10];
ll len[N + 10][N + 10], w[N + 10][N + 10];
ll dis[N + 10][N + 10], e[N + 10][N + 10];
ll x[N + 10][N + 10], y[N + 10][N + 10];

void readInput() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++)
            cin >> b[i][j] >> s[i][j];
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        cin >> e[u][v];
    }
}

void calcFloyd() {
    for (int i = 1; i <= n; i++) {
        dis[i][i] = 0;
        for (int j = 1; j <= n; j++)
            if (j != i)
                dis[i][j] = w[i][j];
    }
    for (int x = 1; x <= n; x++)
        for (int u = 1; u <= n; u++)
            for (int v = 1; v <= n; v++)
                dis[u][v] = min(dis[u][v], dis[u][x] + dis[x][v]);
}

void calcLen() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i][j] = (e[i][j]? e[i][j]: INF);
    calcFloyd();
    for (int i = 1; i <= n; i++)    
        for (int j = 1; j <= n; j++)
            len[i][j] = dis[i][j];
}

void calcXY() {
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++) {
            x[u][v] = -1;
            y[u][v] = len[u][v];
            for (int i = 1; i <= k; i++)
                if (len[u][v] != INF && b[u][i] != -1 && s[v][i] != -1 && s[v][i] > b[u][i]) {
                    x[u][v] = max(x[u][v], s[v][i] - b[u][i]);
                }
            if (len[u][v] != INF) 
                x[u][v] = max(x[u][v], 0ll);
        }   
}

void calcW(ll res) {
    for (int u = 1; u <= n; u++)
        for (int v = 1; v <= n; v++) 
            if (x[u][v] != -1)
                w[u][v] = y[u][v] * res - x[u][v];
            else
                w[u][v] = INF;
}

bool check(ll res) {
    calcW(res);
    calcFloyd();
    for (int i = 1; i <= n; i++) {
        if (dis[i][i] < 0)
            return true;
        for (int j = 1; j <= n; j++)
            if (i != j && dis[i][j] + w[j][i] == 0)
                return true;
    }
    return false;
}

void calcAns() {
    ll l = 0, r = INF9 + 1;
    while (r - l > 1) {
        ll mid = (l + r) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcLen();
    calcXY();
    calcAns();
    return 0;
}

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