제출 #1196846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196846		trufanov.p	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	50 ms	2120 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;

typedef long long ll;

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const ll LLINF = 1e9 + 5;

bool existsNegativeLoop(ll x, const vector<vector<ll>>& profit, const vector<vector<ll>>& dist) {
    int n = profit.size();
    vector<vector<ll>> gr(n, vector<ll>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            gr[i][j] = x * dist[i][j] - profit[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        gr[i][i] = LLINF;
    }
    for (int q = 0; q < n; ++q) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                gr[i][j] = min(gr[i][j], gr[i][q] + gr[q][j]);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (gr[i][i] <= 0) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> buy(n, vector<ll>(k));
    vector<vector<ll>> sell(n, vector<ll>(k));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            cin >> buy[i][j] >> sell[i][j];
        }
    }
    vector<vector<ll>> matr(n, vector<ll>(n, LLINF));
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll t;
        cin >> u >> v >> t;
        matr[u - 1][v - 1] = t;
    }
    for (int i = 0; i < n; ++i) {
        matr[i][i] = 0;
    }
    vector<vector<ll>> dist = matr;
    for (int q = 0; q < n; ++q) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][q] + dist[q][j]);
            }
        }
    }
    vector<vector<ll>> profit(n, vector<ll>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j || dist[i][j] == LLINF) {
                continue;
            }
            for (int q = 0; q < k; ++q) {
                if (buy[i][q] == -1 || sell[j][q] == -1) {
                    continue;
                }
                profit[i][j] = max(profit[i][j], sell[j][q] - buy[i][q]);
            }
        }
    }
    ll l = 0, r = 1e9;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        if (existsNegativeLoop(m, profit, dist)) {
            l = m;
        } else {
            r = m;
        }
    }
    cout << l << '\n';
}

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