Submission #955536

#	Time	Username	Problem	Language	Result	Execution time	Memory
955536		Matjaz	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	135 ms	3520 KiB

merchant

//
//  APIO17_MERCHANT.cpp
//  
//
//  Created by Matjaz Leonardis on 22/03/2024.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,M,K;
long long INF = (1LL<<39);

// If we buy something at u and go to v there will be the perfect item for that and we can take the shortest path there. 

int main(){
    cin >> N >> M >> K;
    
    vector<vector<int> > B(N, vector<int> (K));
    vector<vector<int> > S(N, vector<int> (K));
    
    for (int i=0;i<N;i++){
        for (int j=0;j<K;j++) cin >> B[i][j] >> S[i][j];
    }
    
    vector<vector<long long> > dist(N, vector<long long>(N, INF));
    
    for (int i=0;i<M;i++){
        int V,W,T;
        cin >> V >> W >> T;
        dist[V - 1][W - 1] = T;
    }
    
    for (int k=0;k<N;k++){
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
    
    /*cout << "OG" << endl;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++) cout << dist[i][j] << " ";
        cout << endl;
    }
    cout << endl; */
    
    vector<vector<long long> > profit(N, vector<long long> (N));
    
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            for (int k=0;k<K;k++) if (B[i][k] >= 0) profit[i][j] = max(profit[i][j], (long long)S[j][k] - B[i][k]);
        }
    }
    
    /*cout << "Profit" << endl;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++) cout << profit[i][j] << " ";
        cout << endl;
    }
    cout << endl; */
    
    
    
    long long best = 0;
    
    long long l = 0;
    long long u = 1e9;
    
    while (l < u){
        long long mid = l + (u - l + 1) / 2;
        // Each new edge is profit[i][j] - mid * dist[i][j]
        
        vector<vector<long long> > dist_tmp(N, vector<long long>(N, INF));
        
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) if (dist[i][j] < INF) dist_tmp[i][j] = mid * dist[i][j] - profit[i][j]; // Do we get any blow ups here?
        }
        
       /* cout << mid << endl;
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) cout << dist_tmp[i][j] << " ";
            cout << endl;
        }
        cout << endl; */
        for (int k=0;k<N;k++){
            for (int i=0;i<N;i++){
                for (int j=0;j<N;j++) dist_tmp[i][j] = min(dist_tmp[i][j],dist_tmp[i][k] + dist_tmp[k][j]);
            }
        }
        
        /*cout << mid << endl;
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++) cout << dist_tmp[i][j] << " ";
            cout << endl;
        }
        cout << endl;*/
        
        bool contains_cycle = false;
        
        for (int i=0;i<N;i++) if (dist_tmp[i][i] <= 0) contains_cycle = true;
        
        if (contains_cycle) l = mid; else u = mid - 1;
    
    }
    
    best = l;
    cout << best << endl;
    
    return 0;
}

/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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