제출 #1159887

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

merchant

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
#define pb push_back
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()

const ll BUY_MAX = 1'000'000'000ll;
const ll SELL_MIN = 0ll;
const ll INT_INF = INF(ll) >> 4ll;

/*
check if the graph with weights M*dur - profit
has a nonpositive cycle
*/
bool good(ll n, ll m, ll k, ll M, const vvll& dur, const vvll& profits) {
    vvll dist;
    for(ll i = 0ll; i < n; i++) {
        vll distr(n, INT_INF);
        dist.pb(distr);
    }

    // Initialize distance array

    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            // if(dur[i][j] >= INT_INF || dur[j][i] >= INT_INF) continue;
            // if(i == j) continue;
            
            dist[i][j] = M * min(dur[i][j], INT_INF / M) - profits[i][j];
        }
    }

    // Apply Floyd-warshall

    // for(ll rep = 0ll; rep < 2ll; rep++) {
    for(ll k = 0ll; k < n; k++) {
        for(ll i = 0ll; i < n; i++) {
            for(ll j = 0ll; j < n; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // }

    // for(ll i = 0ll; i < n; i++) {
    //     for(ll j = 0ll; j < n; j++) {
    //         cerr << dist[i][j] << " ";
    //     }
    //     cerr << "\n";
    // }
    // cerr << "\n";

    for(ll i = 0ll; i < n; i++) if(dist[i][i] <= 0ll) return true;
    return false;
}

int main() {
    ll n, m, k;
    cin >> n >> m >> k;

    // Input the prices
    vvpll market;
    for(ll i = 0ll; i < n; i++) {
        vpll prices;
        for(ll j = 0ll; j < k; j++) {
            ll b, s;
            cin >> b >> s;

            // if(b == -1ll) b = BUY_MAX;
            // if(s == -1ll) s = SELL_MIN;

            prices.pb({b, s});
        }

        market.pb(prices);
    }

    // Input the weights in the adjacency matrix
    vvll dist;
    for(ll i = 0ll; i < n; i++) {
        vll distr(n, INT_INF);
        dist.pb(distr);
    }

    for(ll i = 0ll; i < n; i++) dist[i][i]= 0ll;

    for(ll i = 0ll; i < m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;

        dist[u][v] = w;
    }

    for(ll k = 0ll; k < n; k++) {
        for(ll i = 0ll; i < n; i++) {
            for(ll j = 0ll; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    // Preprocess shortest paths and max profits
    vvll profits;
    for(ll i = 0ll; i < n; i++) {
        vll profitsr(n, 0ll);
        profits.pb(profitsr);
    }

    // profits[buy][sell]
    for(ll i = 0ll; i < n; i++) {
        for(ll j = 0ll; j < n; j++) {
            if(i == j) continue;

            for(ll kp = 0ll; kp < k; kp++) {
                if(market[j][kp].second != -1ll && market[i][kp].first != -1ll) profits[i][j] = max(profits[i][j], market[j][kp].second - market[i][kp].first);
            }
        }
    }

    /// Shortest paths
    ll l = -1ll, r = 1'000'000'001ll;

    while(r - l > 1ll) {
        ll M = (l + r) >> 1ll;

        if(good(n, m, k, M, dist, profits)) l = M;
        else r = M;
    }

    cout << max(l, 0ll) << endl;

    return 0;
}

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