Submission #1117025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117025		hyakup	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	84 ms	3912 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const int maxn = 1e2 + 10;
const int maxk = 1e3 + 10;
const ll inf = 1e9 + 10;

ll tempo[maxn][maxn], lucro[maxn][maxn], dist[maxn], buy[maxn][maxk], sell[maxn][maxk];
bool marc[maxn];

vector<pair<int, ll>> adj[maxn];

void dijkstra( int source ){
    set<pair<ll, int>> s;
    for( int i = 0; i < maxn; i++ ) tempo[source][i] = inf;
    tempo[source][source] = 0;
    s.insert({ 0, source });
    while( !s.empty() ){
        int cur = s.begin()->second; s.erase(s.begin());
        for( auto [viz, d] : adj[cur] ) if( tempo[source][viz] > tempo[source][cur] + d ){
            s.erase({ tempo[source][viz], viz });
            tempo[source][viz] = tempo[source][cur] + d;
            s.insert({ tempo[source][viz], viz });
        }
    }
}

void bellman_ford( int n ){
    for( int i = 1; i <= n; i++ ) dist[i] = inf;
    dist[1] = 0;
    for( int i = 1; i <= n; i++ ){
        // cout << "distancias " << endl;
        // for( int cur = 1; cur <= n; cur++ ) cout << dist[cur] << " ";
        // cout << endl;
        for( int cur = 1; cur <= n; cur++ )
            for( auto [viz, d] : adj[cur] ) dist[viz] = min( dist[viz], dist[cur] + d );
    }
}

bool dfs( int cur ){
    if( marc[cur] ) return true;
    marc[cur] = true;
    for( auto [viz, d] : adj[cur] ) if( dist[viz] == dist[cur] + d && dfs( viz ) ) return true;
    return false;
}

bool check_negative_cicle( int n, ll val ){
    // bug(val);
    for( int i = 1;i <= n; i++ ){
        adj[i].clear();
        for( int j = 1; j <= n; j++ ) if( i != j ){
            adj[i].push_back({ j, tempo[i][j]*val - lucro[i][j] });
            // cout << i << " -> " << j << " -------- " <<  tempo[i][j]*val - lucro[i][j] << endl;
        }
    }

    bellman_ford( n );
    for( int i = 1; i <= n; i++ ) marc[i] = false;
    for( int i = 1; i <= n; i++ ){
        if( !marc[i] && dfs( i ) ) return true;
        for( auto [viz, d] : adj[i] ) if( dist[viz] > dist[i] + d ) return true;
    }
    return false;
}

ll bs( int n ){
    ll l = 0, r = inf;///////////////////////////////////////////////////////////////////////////////////
    while( l < r ){
        ll mid = ( l + r + 1 )/2;
        if( check_negative_cicle( n, mid ) ) l = mid;
        else r = mid - 1;
    } return l;
}

int main(){
    int n, m, k; 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 = 1; i <= m; i++ ){
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({ b, c });
    }

    // get distances
    for( int i = 1; i <= n; i++ ){
        dijkstra( i );
        for( int j = 1; j <= n; j++ ) if( j != i ){
            for( int item = 1; item <= k; item++ ) if( buy[i][item] != -1 && sell[j][item] != -1 ) lucro[i][j] = max( lucro[i][j], sell[j][item] - buy[i][item] );
        }
    }
    // 
    // for( int i = 1; i <= n;i++ ) for( int j = 1; j <= n; j++ ) if( i != j ){
    //     // cout << i << " " << j << ":" << endl;
    //     bug(tempo[i][j]);
    //     bug(lucro[i][j]);
    // }

    cout << bs( n ) << endl;
}

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