Submission #818052

#	Time	Username	Problem	Language	Result	Execution time	Memory
818052		Ozy	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	71 ms	4148 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a <<  " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli> 

#define MAX 100
#define INF (1ll<<60)

lli n,m,k,res,a,b,c,prod;
lli dis[MAX+2][MAX+2],profit[MAX+2][MAX+2],otro[MAX+2][MAX+2];
lli compras[MAX+2][1002],ventas[MAX+2][1002];

void floyd_warshall(lli g[MAX+2][MAX+2]) {
    rep(i,1,n) 
        rep(j,1,n)
            rep(k,1,n) 
                g[j][k] = min(g[j][k], g[j][i]+g[i][k]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> prod;
    rep(i,1,n) {
        rep(j,1,n) dis[i][j] = INF;
        rep(j,1,prod) cin >> compras[i][j] >> ventas[i][j];
    }
    rep(i,1,m) {
        cin >> a >> b >> c;
        dis[a][b] = c;
    }
    floyd_warshall(dis);  //si se pasa por referencia

    //defino el arreglo de profits con otro floyd_warshall

    rep(i,1,n)
        rep(j,1,n)
            rep(k,1,prod) {
                if(compras[i][k] == -1 || ventas[j][k] == -1) continue;
                profit[i][j] = max(profit[i][j], ventas[j][k] - compras[i][k]);
            }

    lli mitad,ini = 1;
    lli fin = (1ll<<30);
    while (ini <= fin) {
        mitad = (ini+fin)/2;
        rep(i,1,n) 
            rep(j,1,n) 
                otro[i][j] = mitad * min(dis[i][j], INF/mitad) - profit[i][j];

        floyd_warshall(otro);
        bool ciclo_neg = false;
        rep(i,1,n) if(otro[i][i] <= 0) ciclo_neg = true;
        if (ciclo_neg) {
            ini = mitad + 1;
            res = mitad;
        }
        else fin = mitad-1;
    }
    
    cout << res;

    return 0;
}
//checar lo de pasar el arreglo por referencia

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