Submission #907675

#	Time	Username	Problem	Language	Result	Execution time	Memory
907675		shezitt	Travelling Merchant (APIO17_merchant)	C++14	33 / 100	92 ms	2340 KiB

merchant

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll 
#define ii pair<int,int>

const int N = 105;
const int K = 1010;
const int INF = 1e18 / 2;

int buy[N][K];
int sell[N][K];

int n, m, k;

int dis[N][N];
int profit[N][N];
int ngraph[N][N];

signed main(){
    cin >> n >> m >> k;
    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<n; ++i){
        for(int j=0; j<n; ++j){
            dis[i][j] = INF;
        }
    }
    for(int i=0; i<m; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        dis[u][v] = min(dis[u][v], w);
    }

    for(int u=0; u<n; ++u){
        for(int v=0; v<n; ++v){
            for(int p=0; p<n; ++p){
                dis[u][v] = min(dis[u][v], dis[u][p] + dis[p][v]);
            }
        }
    }
    for(int i=0; i<n; ++i){
        for(int j=0; j<n; ++j){
            for(int l=0; l<k; ++l){
                if(sell[j][l] != -1 && buy[i][l] != -1){
                    profit[i][j] = max(profit[i][j], sell[j][l] - buy[i][l]);
                }
            }
        }
    }

    int ans = -1;
    int low = 1, high = 1e9;
    while(low <= high){
        int mid = low + (high - low) / 2;
        for(int i=0; i<n; ++i){
            for(int j=0; j<n; ++j){
                // ngraph[i][j] = profit[i][j] - dis[i][j] * mid;
                ngraph[i][j] = mid * min(INF / mid, dis[i][j]) - profit[i][j];
            }
            // ngraph[i][i] = -1;
        }

        for(int u=0; u<n; ++u){
            for(int v=0; v<n; ++v){
                for(int p=0; p<n; ++p){
                    // ngraph[u][v] = max(ngraph[u][v], ngraph[u][p] + ngraph[p][v]);
                    ngraph[u][v] = min(ngraph[u][v], ngraph[u][p] +ngraph[p][v]);
                }
            }
        }

        bool ok = 0;
        for(int i=0; i<n; ++i){
            if(ngraph[i][i] <= 0){
                ok = 1;
            }
        }

        if(ok){
            low = mid+1;
            ans = mid;
        } else {
            high = mid-1;
        }

    }

    cout << ans << endl;

}

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