Submission #57835

#	Time	Username	Problem	Language	Result	Execution time	Memory
57835		Jeez	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	88 ms	2040 KiB

merchant

#include <iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e10;
const int MAX_N = 100 + 9;
const int MAX_K = 1000 + 9;
int n, m, K;
ll buy[MAX_N][MAX_K], sell[MAX_N][MAX_K];
ll w[MAX_N][MAX_N], dist[MAX_N][MAX_N], profit[MAX_N][MAX_N];
ll g[MAX_N][MAX_N], g2[MAX_N][MAX_N];

void read(){
    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 = 0; i < m; i++){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        dist[u][v] = w;
    }
}

void init(){
    for(int i = 1; i < MAX_N; i++){
        for(int j = 1; j < MAX_N; j++)
            dist[i][j] = INF;
        dist[i][i] = 0;
    }
}

void floyd(){
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

bool check(ll rat){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dist[i][j] == INF)
                g[i][j] = -INF;
            else
                g[i][j] = profit[i][j] - dist[i][j] * rat;
            g[i][i] = -INF;
        }
    }

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                g[i][j] = max(g[i][j], g[i][k] + g[k][j]);
                if(g[i][i] >= 0)
                    return true;
            }

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            g2[i][j] = g[i][j];

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++){
                g2[i][j] = max(g2[i][j], g2[i][k] + g2[k][j]);
                if(g2[i][j] > g[i][j])
                    return true;
            }

    return false;
}

void solve(){
    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) continue;
                profit[i][j] = max(profit[i][j], sell[j][k] - buy[i][k]);
            }

    ll lo = 1, hi = 1e18, mid, ans = 0;
    while(lo <= hi){
        mid = (lo + hi) / 2;
        if(check(mid)){
            ans = mid;
            lo = mid + 1;
        } else
            hi = mid - 1;
    }

    cout << ans << '\n';
}

int main()
{
    init();
    read();
    floyd();
    solve();
    return 0;
}

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