제출 #1160547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160547		jus_teng	여행하는 상인 (APIO17_merchant)	C++20	0 / 100	1095 ms	2756 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);
    vector<ld> dist(v, -inf);
    
    // Initialize starting states (no item at each market)
    for (ll u = 0; u < n; u++) {
        dist[u * (k + 1)] = 0; // No item state
    }
    
    // Bellman-Ford: V-1 relaxations
    for (ll iter = 0; iter < v - 1; iter++) {
        bool updated = false;
        for (ll u = 0; u < n; u++) {
            ll uNoItem = u * (k + 1);
            // Buy an item
            for (ll j = 0; j < k; j++) {
                if (b[u][j] != -1) {
                    ll uWithJ = u * (k + 1) + (j + 1);
                    ld weight = -b[u][j];
                    if (dist[uNoItem] > -inf && dist[uNoItem] + weight > dist[uWithJ] + eps) {
                        dist[uWithJ] = dist[uNoItem] + weight;
                        updated = true;
                    }
                }
            }
            // Sell an item
            for (ll j = 0; j < k; j++) {
                ll uWithJ = u * (k + 1) + (j + 1);
                if (s[u][j] != -1 && dist[uWithJ] > -inf) {
                    ld weight = s[u][j];
                    if (dist[uWithJ] + weight > dist[uNoItem] + eps) {
                        dist[uNoItem] = dist[uWithJ] + weight;
                        updated = true;
                    }
                }
            }
            // Move with current item state
            for (auto p : adj[u]) {
                ll vMarket = p.first;
                ll travelTime = p.second;
                for (ll c = 0; c <= k; c++) {
                    ll uState = u * (k + 1) + c;
                    ll vState = vMarket * (k + 1) + c;
                    ld weight = -lambda * travelTime;
                    if (dist[uState] > -inf && dist[uState] + weight > dist[vState] + eps) {
                        dist[vState] = dist[uState] + weight;
                        updated = true;
                    }
                }
            }
        }
        if (!updated) break; // Early exit if no changes
    }
    
    // Check for positive cycles
    for (ll u = 0; u < n; u++) {
        ll uNoItem = u * (k + 1);
        for (ll j = 0; j < k; j++) {
            if (b[u][j] != -1) {
                ll uWithJ = u * (k + 1) + (j + 1);
                ld weight = -b[u][j];
                if (dist[uNoItem] + weight > dist[uWithJ] + eps) {
                    return true;
                }
            }
            ll uWithJ = u * (k + 1) + (j + 1);
            if (s[u][j] != -1 && dist[uWithJ] > -inf) {
                ld weight = s[u][j];
                if (dist[uWithJ] + weight > dist[uNoItem] + eps) {
                    return true;
                }
            }
        }
        for (auto p : adj[u]) {
            ll vMarket = p.first;
            ll travelTime = p.second;
            for (ll c = 0; c <= k; c++) {
                ll uState = u * (k + 1) + c;
                ll vState = vMarket * (k + 1) + c;
                ld weight = -lambda * travelTime;
                if (dist[uState] > -inf && dist[uState] + weight > dist[vState] + eps) {
                    return true;
                }
            }
        }
    }
    return false;
}

ll solve() {
    ld low = 0.0;
    ld high = 1e12;
    for (int iter = 0; iter < 50; iter++) { // Reduced to 50 for speed
        ld mid = (low + high) / 2.0;
        if (check(mid)) {
            low = mid;
        } else {
            high = mid;
        }
    }
    if (!check(low)) return 0;
    return (ll)floor(low + eps); // Ensure rounding handles floating-point precision
}

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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