Submission #882794

#	Time	Username	Problem	Language	Result	Execution time	Memory
882794		vjudge1	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	70 ms	2272 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define endl '\n'
#define ll long long
#define int ll
#define pii pair <int, int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846

const int N = 105, K = 1005;
const int mod = 1e9 + 7;
const int INF = 1e18;

int n, m, p;
int buy[N][K], sell[N][K], prof[N][N], a[N][N], dis[N][N], cur[N][N];

signed main() {
    io;
    cin >> n >> m >> p;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < p; 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 x, y, z;
        cin >> x >> y >> z;
        x--;
        y--;
        a[x][y] = z;
        dis[x][y] = z;
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dis[i][k] < INF && dis[k][j] < INF){
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < p; k++){
                if(buy[i][k] != -1 && sell[j][k] != -1){
                    prof[i][j] = max(prof[i][j], sell[j][k] - buy[i][k]);
                }
            }
        }
    }
    int l = 0, r = mod, ans = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                cur[i][j] = INF;
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dis[i][j] * mid < INF) cur[i][j] = mid * dis[i][j] - prof[i][j];
            }
        }
        for(int k = 0; k < n; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(cur[i][k] < INF && cur[k][j] < INF){
                        cur[i][j] = min(cur[i][j], cur[i][k] + cur[k][j]);
                    }
                }
            }
        }
        bool ok = false;
        for(int i = 0; i < n; i++){
            if(cur[i][i] <= 0) ok = true;
        }
        if(ok){
            ans = max(ans, mid);
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    cout << ans << endl;
}

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