Submission #512323

#	Time	Username	Problem	Language	Result	Execution time	Memory
512323		InternetPerson10	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	1097 ms	2112 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<vector<ll>> b, s;
vector<vector<pair<int, int>>> adj;
ll dist[100][100], gain[100][100];
ll recip[100][100];

const ll BIG = 1234567891234567890;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int n, m, k;
    cin >> n >> m >> k;
    b.resize(n);
    s.resize(n);
    adj.resize(n);
    for(int i = 0; i < n; i++) {
        b[i].resize(k);
        s[i].resize(k);
        for(int j = 0; j < k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
        for(int j = 0; j < n; j++) {
            dist[i][j] = BIG;
            gain[i][j] = 0;
        }
    }
    for(int i = 0; i < m; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        x--; y--;
        adj[x].push_back({y, t});
        dist[x][y] = t;
    }
    // floyd-warshall
    for(int z = 0; z < n; z++) {
        for(int x = 0; x < n; x++) {
            for(int y = 0; y < n; y++) {
                dist[x][y] = min(dist[x][y], dist[x][z] + dist[z][y]);
            }
        }
    }
    // gain calculation
    for(int x = 0; x < n; x++) {
        for(int y = 0; y < n; y++) {
            for(int i = 0; i < k; i++) {
                if(b[x][i] == -1 || s[y][i] == -1) continue;
                gain[x][y] = max(gain[x][y], s[y][i] - b[x][i]);
            }
        }
    }
    int l = 0, r = 1234567890;
    while(l != r - 1) {
        int mid = (l+r)/2;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) recip[i][j] = BIG;
                else recip[i][j] = dist[i][j] * mid - gain[i][j];
            }
        }
        ll ans = 1;
        for(int z = 0; z < n; z++) {
            for(int x = 0; x < n; x++) {
                for(int y = 0; y < n; y++) {
                    recip[x][y] = min(recip[x][y], recip[x][z] + recip[z][y]);
                }
            }
        }
        for(int x = 0; x < n; x++) {
            for(int y = 0; y < n; y++) {
                ans = min(ans, recip[x][y] + recip[y][x]);
            }
        }
        if(ans <= 0) l = mid;
        else r = mid;
    }
    cout << l << '\n';
}

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