Submission #1123530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123530		hmm789	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	77 ms	2224 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, k, x, y, z;
    cin >> n >> m >> k;
    int b[n][k], s[n][k], w[n][n], p[n][n];
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) w[i][j] = INF;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < k; j++) cin >> b[i][j] >> s[i][j];
    }
    for(int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        x--; y--;
        w[x][y] = z;
    }
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
            }
        }
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
        p[i][j] = 0;
        for(int it = 0; it < k; it++) if(s[j][it] != -1 && b[i][it] != -1) {
            p[i][j] = max(p[i][j], s[j][it] - b[i][it]);
        }
    }
    int l = 0, r = INF, md;
    while(l < r) {
        md = (l+r)/2;
        int dist[n][n];
        for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
            dist[i][j] = w[i][j]*md - p[i][j];
        }
        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]);
                }
            }
        }
        bool ok = false;
        for(int i = 0; i < n; i++) if(dist[i][i] <= 0) ok = true;
        if(ok) l = md+1;
        else r = md;
    }
    cout << l-1 << '\n';
}

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