Submission #698148

#	Time	Username	Problem	Language	Result	Execution time	Memory
698148		sharaelong	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	99 ms	2816 KiB

merchant

#include <bits/stdc++.h>
#include <vector>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 100;
const int MAX_K = 1000;
const int INF = 0x3f3f3f3f;

int d[MAX_N][MAX_N];
pii price[MAX_N][MAX_K];
int max_profit[MAX_N][MAX_N];

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<k; ++j) {
            cin >> price[i][j].first >> price[i][j].second;
        }
    }
    for (int i=0; i<MAX_N; ++i) {
        for (int j=0; j<MAX_N; ++j) {
            d[i][j] = (i == j ? 0 : INF);
        }
    }
    for (int i=0; i<m; ++i) {
        int v, w, t;
        cin >> v >> w >> t;
        d[v-1][w-1] = t;
    }
    for (int k=0; k<n; ++k) {
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            for (int l=0; l<k; ++l) {
                if (price[i][l].first != -1 && price[j][l].second != -1) {
                    max_profit[i][j] = max(max_profit[i][j], price[j][l].second - price[i][l].first);
                }
            }
        }
    }

    int l = 0, r = INF;
    while (l < r) {
        int m = (l+r+1) / 2;
        vector<tuple<int, int, ll>> edges;
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                if (i != j && d[i][j] < INF) {
                    ll minw = 4e18;
                    for (int p=0; p<n; ++p) {
                        if (d[i][p] < INF && d[p][j] < INF) {
                            minw = min(minw, (ll)m * (d[i][p] + d[p][j]) - max_profit[i][p]);
                        }
                    }
                    edges.push_back({ i, j, minw });
                }
            }
        }
        // print(edges);

        bool neg_cycle = false;
        vector<ll> dist(n, 4e18);
        for (int i=0; i<n; ++i) {
            bool reduced = false;
            for (auto[a,b,w]: edges) {
                if (dist[b] > dist[a] + w) {
                    dist[b] = dist[a] + w;
                    reduced = true;
                }
            }
            if (i == n-1 && reduced) neg_cycle = true;
        }

        if (!neg_cycle) {
            vector<vector<int>> adj(n);
            for (auto[a,b,w]: edges) {
                if (dist[b] == dist[a] + w) adj[a].push_back(b);
            }
            
            bool cycle_exist = false;
            vector<int> visited(n, -1);
            for (int i=0; i<n; ++i) {
                if (visited[i] == -1) {
                    queue<int> q;
                    visited[i] = 0;
                    q.push(i);
                    while (!q.empty()) {
                        int here = q.front();
                        q.pop();
                        for (int there: adj[here]) {
                            if (visited[there] != -1) {
                                if (visited[there] < visited[here]) cycle_exist = true;
                            } else {
                                q.push(there);
                                visited[there] = visited[here] + 1;
                            }
                        }
                        if (cycle_exist) break;
                    }
                    if (cycle_exist) break;
                }
            }
            if (cycle_exist) {
                l = m;
            } else {
                r = m-1;
            }
        } else {
            l = m;
        }
        
    }
    cout << l;
}

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

    solve();
}

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