제출 #1158120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158120		jasonic	여행하는 상인 (APIO17_merchant)	C++20	0 / 100	27 ms	836 KiB

merchant

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

bool condition(ll n, vector<vector<ll>> lengths) {
    for(ll j = 0; j < n; j++) { // inside node
        for(ll i = 0; i < n; i++) {
            for(ll k = 0; k < n; k++) {
                lengths[i][k] = min(lengths[i][k], lengths[i][j] + lengths[j][k]);
            }
        }
    }
    
    bool isCorrect = false;

    for(ll i = 0; i < n; i++) if(lengths[i][i] <= 0) isCorrect = true;

    return isCorrect;
}

int main() {
    fastIO;
    
    ll N, M, K; cin >> N >> M >> K;
    vector<vector<ll>> buy(N, vector<ll>(N, 0ll));
    vector<vector<ll>> sell(N, vector<ll>(N, 0ll));
    vector<vector<ll>> edges(N, vector<ll>(N, (ll)1e15));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < K; j++) {
            cin >> buy[i][j] >> sell[i][j];
        }
    }

    for(int i = 0; i < M; i++) {
        ll a, b, w; cin >> a >> b >> w;
        a--;b--;
        edges[a][b] = w;
    }

    // initial floyd-warshall on the edges

    for(int j = 0; j < N; j++) {
        for(int i = 0; i < N; i++) {
            for(int k = 0; k < N; k++) {
                edges[i][k] = min(edges[i][k], edges[i][j] + edges[j][k]);
            }
        }
    }

    vector<vector<ll>> profit(N, vector<ll>(N, 0ll));

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

    // binary search the valid value
    ll l = 0, r = 1e9 + 1;

    vector<vector<ll>> actualEdges(N, vector<ll>(N, 0));

    while(l + 1 < r) {
        ll m = (l+r)>>1ll;

        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                actualEdges[i][j] = (m * min(edges[i][j], (ll)1e15)) - profit[i][j];
            }
        }

        if (condition(N, actualEdges)) { // that means that the answer is valid
            l = m;
        } else {
            r = m;
        }
    }

    cout << l << '\n';

    return 0;
}

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