Submission #1160549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160549		jus_teng	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1096 ms	3644 KiB

merchant

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

typedef long long ll;
typedef double ld;

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

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

bool check(ld lambda) {
    ll v = n * (k + 1); // States: (market, item or no item)
    vector<ld> dist(v, -inf);
    vector<int> visitCount(v, 0);
    vector<bool> inQueue(v, false);
    queue<ll> q;

    // Start with no item at each market
    for (ll u = 0; u < n; u++) {
        dist[u * (k + 1)] = 0; // No item state
        q.push(u * (k + 1));
        inQueue[u * (k + 1)] = true;
    }

    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        inQueue[u] = false;

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

        // Buy only at market 0 (1-based market 1)
        if (currentMarket == 0 && itemState == 0) {
            for (ll j = 0; j < k; j++) {
                if (b[0][j] != -1) {
                    ll nextState = currentMarket * (k + 1) + (j + 1);
                    ld weight = -b[0][j]; // Buying cost
                    if (dist[u] + weight > dist[nextState] + eps) {
                        dist[nextState] = dist[u] + weight;
                        if (!inQueue[nextState]) {
                            q.push(nextState);
                            inQueue[nextState] = true;
                            visitCount[nextState]++;
                            if (visitCount[nextState] > v) return true;
                        }
                    }
                }
            }
        }
        // Sell at any market
        else if (itemState > 0) {
            ll j = itemState - 1;
            if (s[currentMarket][j] != -1) {
                ll nextState = currentMarket * (k + 1); // Back to no item
                ld weight = s[currentMarket][j]; // Selling profit
                if (dist[u] + weight > dist[nextState] + eps) {
                    dist[nextState] = dist[u] + weight;
                    if (!inQueue[nextState]) {
                        q.push(nextState);
                        inQueue[nextState] = true;
                        visitCount[nextState]++;
                        if (visitCount[nextState] > v) return true;
                    }
                }
            }
        }

        // Move to next market
        for (auto p : adj[currentMarket]) {
            ll nextMarket = p.first;
            ll travelTime = p.second;
            ll nextState = nextMarket * (k + 1) + itemState;
            ld weight = -lambda * travelTime;
            if (dist[u] > -inf && dist[u] + weight > dist[nextState] + eps) {
                dist[nextState] = dist[u] + weight;
                if (!inQueue[nextState]) {
                    q.push(nextState);
                    inQueue[nextState] = true;
                    visitCount[nextState]++;
                    if (visitCount[nextState] > v) return true;
                }
            }
        }
    }
    return false;
}

ll solve() {
    ld low = 0.0;
    ld high = 1e9; // Tight bound based on constraints
    for (int iter = 0; iter < 50; iter++) {
        ld mid = (low + high) / 2.0;
        if (check(mid)) low = mid;
        else high = mid;
    }
    if (!check(low)) return 0;
    return (ll)floor(low + eps);
}

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

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

    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", solve());
    return 0;
}

Compilation message (stderr)

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

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