Submission #885173

#	Time	Username	Problem	Language	Result	Execution time	Memory
885173		Pikachu	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	136 ms	4648 KiB

merchant

#include <bits/stdc++.h>
#define int long long

using namespace std;

template<typename T>
inline bool maxi(T &x, const T &val)
{
    if (x < val) return x = val, true;
    return false;
}

template<typename T>
inline bool mini(T &x, const T &val)
{
    if (x > val) return x = val, true;
    return false;
}

const int maxn = 110, maxk = 1010, oo = 1e18;
int n, m, k;
int b[maxn][maxk], s[maxn][maxk];
vector<pair<int,int> > adj[maxn];
int d[maxn][maxn];
int pro[maxn][maxn];

priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;

void Dijkstra(int st, int d[])
{
    d[st] = 0;
    pq.push({0, st});
    while (!pq.empty()) {
        int wei = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if (d[cur] != wei) continue;

        for (auto [v, w] : adj[cur]) {
            if (mini(d[v], wei + w)) {
                pq.push({d[v], v});
            }
        }
    }
}

int dp[maxn][maxn];

bool check(int mid)
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = pro[i][j] - mid * d[i][j];
        }
    }
    for (int x = 1; x <= n; x++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                maxi(dp[i][j], dp[i][x] + dp[x][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dp[i][i] >= 0) {
            return true;
        }
    }
    return false;
}

void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
    }
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = 1e9;
        }
    }
    for (int i = 1; i <= n; i++) {
        Dijkstra(i, d[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                pro[i][j] = -oo;
                continue;
            }
            int &tmp = pro[i][j];
            for (int x = 1; x <= k; x++) {
                if (s[j][x] != -1 && b[i][x] != -1 && s[j][x] > b[i][x]) {
                    maxi(tmp, s[j][x] - b[i][x]);
                }
            }
        }
    }
    int l = 0;
    int r = 1e9;
    int ans = l;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << '\n';
}

signed main()
{
#ifdef LOCAL
    clock_t st = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);

#define Task ""
#ifdef LOCAL
    if (!fopen("D:\\.inp", "r")) {
        freopen("D:\\.inp", "w", stdout);
        freopen("D:\\.out", "w", stdout);
        cerr << "get input from file\n";
        return 0;
    }
    freopen("D:\\.inp", "r", stdin);
    freopen("D:\\.out", "w", stdout);
#else
    if (fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
#endif

    solve();

#ifdef LOCAL
    cerr << clock() - st << endl;
#endif
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(Task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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