Submission #1160541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160541		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1095 ms	3564 KiB

merchant

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

/* SPFA algorithm adapted from https://cp-algorithms.com/graph/bellman_ford.html
   Binary Search algorithm adapted from https://cp-algorithms.com/num_methods/binary_search.html
   Modifications:
   - Transformed state space where each node is (market, item state)
   - Total number of states is n * (k + 1)
   - k + 1 represents the item purchase states
   - Use deque
   - Increased cycle detection threshold
*/

typedef long long ll;
typedef double ld;

const ll maxN = 100;
const ll maxK = 1000;
const ld inf = 1e18;
const ld eps = 1e-12;

ll n, m, k;
vector<vector<pair<ll, ll>>> adj;
vector<vector<ll>> b, s;

bool SPFA(ld lambda) {
    ll v = n * (k + 1);
    vector<ld> dist(v, 0);
    vector<int> visitCount(v, 0);
    vector<bool> inQueue(v, false);
    deque<int> dq; // Using deque for SLF optimization

    // Initialize queue with all nodes
    for (ll i = 0; i < v; i++) {
        dq.push_back(i);
        inQueue[i] = true;
        visitCount[i] = 1;
    }

    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        inQueue[u] = false;

        ll currentMarket = u / (k + 1);
        ll itemState = u % (k + 1);

        // If no item owned, consider buying items
        if (itemState == 0) {
            for (ll j = 0; j < k; j++) {
                if (b[currentMarket][j] != -1) {
                    ll nextState = currentMarket * (k + 1) + (j + 1);
                    ld weight = -b[currentMarket][j] + eps;

                    if (dist[u] + weight > dist[nextState] + eps) {
                        dist[nextState] = dist[u] + weight;
                        if (!inQueue[nextState]) {
                            if (!dq.empty() && dist[nextState] > dist[dq.front()])
                                dq.push_front(nextState);
                            else
                                dq.push_back(nextState);
                            inQueue[nextState] = true;
                            visitCount[nextState]++;
                            if (visitCount[nextState] > 2 * v) return true; // Cycle detected
                        }
                    }
                }
            }
        } 
        // If an item is owned, consider selling it
        else {
            ll j = itemState - 1;
            if (s[currentMarket][j] != -1) {
                ll nextState = currentMarket * (k + 1);
                ld weight = s[currentMarket][j] + eps;

                if (dist[u] + weight > dist[nextState] + eps) {
                    dist[nextState] = dist[u] + weight;
                    if (!inQueue[nextState]) {
                        if (!dq.empty() && dist[nextState] > dist[dq.front()])
                            dq.push_front(nextState);
                        else
                            dq.push_back(nextState);
                        inQueue[nextState] = true;
                        visitCount[nextState]++;
                        if (visitCount[nextState] > 2 * v) return true; // Cycle detected
                    }
                }
            }
        }

        // Travel to other markets
        for (auto p : adj[currentMarket]) {
            ll nextMarket = p.first;
            ll travelTime = p.second;
            ll nextState = nextMarket * (k + 1) + itemState;
            ld weight = -lambda * travelTime + eps;

            if (dist[u] + weight > dist[nextState] + eps) {
                dist[nextState] = dist[u] + weight;
                if (!inQueue[nextState]) {
                    if (!dq.empty() && dist[nextState] > dist[dq.front()])
                        dq.push_front(nextState);
                    else
                        dq.push_back(nextState);
                    inQueue[nextState] = true;
                    visitCount[nextState]++;
                    if (visitCount[nextState] > 2 * v) return true; // Cycle detected
                }
            }
        }
    }
    
    return false;
}

ll binSearch() {
    ld low = 0.0, high = 1e12;

    for (int iter = 0; iter < 100; iter++) {
        ld mid = (low + high) / 2.0;
        if (SPFA(mid))
            low = mid;
        else
            high = mid;
    }

    return (ll)floor(low);
}

int main() {
    scanf("%lld %lld %lld", &n, &m, &k);
    b.assign(n, vector<ll>(k));
    s.assign(n, vector<ll>(k));
    adj.resize(n);

    // Read buying and selling prices
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < k; j++) {
            scanf("%lld %lld", &b[i][j], &s[i][j]);
        }
    }

    // Read market connections
    for (ll i = 0; i < m; i++) {
        ll from, to, time;
        scanf("%lld %lld %lld", &from, &to, &time);
        adj[from - 1].emplace_back(to - 1, time);
    }

    printf("%lld\n", binSearch());
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     scanf("%lld %lld %lld", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:140:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |             scanf("%lld %lld", &b[i][j], &s[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:147:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         scanf("%lld %lld %lld", &from, &to, &time);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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