Submission #370725

#	Time	Username	Problem	Language	Result	Execution time	Memory
370725		mihai145	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	99 ms	2156 KiB

merchant

//
// Created by mihai145 on 24.02.2021.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 100;
const int KMAX = 1000;
const long long INF = 1e9;

int N, M, K;
long long buy[NMAX + 2][KMAX + 2], sell[NMAX + 2][KMAX + 2];
long long bestProfit[NMAX + 2][NMAX + 2], minTime[NMAX + 2][NMAX + 2];

void CalcBestProfit() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= K; k++) {
                if (sell[j][k] != -1 && buy[i][k] != -1) {
                    bestProfit[i][j] = max(bestProfit[i][j], sell[j][k] - buy[i][k]);
                }
            }
        }
    }
}

void CalcMinTime() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                minTime[i][j] = min(minTime[i][j], minTime[i][k] + minTime[k][j]);
            }
        }
    }
}

long long mt[NMAX + 2][NMAX + 2];

bool Can(long long R) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            mt[i][j] = bestProfit[i][j] - R * minTime[i][j];
        }
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                mt[i][j] = max(mt[i][j], mt[i][k] + mt[k][j]);
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        if (mt[i][i] >= 0) {
            return true;
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M >> K;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            cin >> buy[i][j] >> sell[i][j];
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            minTime[i][j] = INF;
        }
    }
    for (int i = 1; i <= M; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        minTime[u][v] = t;
    }

    CalcBestProfit();
    CalcMinTime();

    long long st = 0, dr = INF, sol = 0;

    while (st <= dr) {
        long long mid = (st + dr) >> 1;

        if (Can(mid)) {
            sol = mid;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }

    cout << sol << '\n';
    return 0;
}

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