Submission #1090382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090382		makrav	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	97 ms	3408 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll

const int INF = 1e9 + 1;

vector<int> dijkstra(int n, vector<vector<pair<int, int>>> g, int s) {
    vector<int> dist(n, INF);
    dist[s] = 0ll;
    set<pair<int, int>> st;
    for (int i = 0; i < n; i++) st.insert({dist[i], i});
    while (!st.empty()) {
        auto [d, v] = *st.begin();
        st.erase({d, v});
        for (auto &[u, w] : g[v]) {
            if (dist[u] > d + w) {
                st.erase({dist[u], u});
                dist[u] = d + w;
                st.insert({dist[u], u});
            }
        }
    }
    return dist;
}

void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>> b(n, vector<int>(k)), s(n, vector<int>(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            cin >> b[i][j] >> s[i][j];
        }
    }
    vector<vector<int>> maxprof(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            for (int kk = 0; kk < k; kk++) {
                //cout << i << ' ' << j << '\n';
                if (b[i][kk] != -1 && s[j][kk] != -1) {
                    maxprof[i][j] = max(maxprof[i][j], s[j][kk] - b[i][kk]);
                }
            }
        }
    }
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << maxprof[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        g[u].pb({v, w});
    }
    vector<vector<int>> dj(n, vector<int>(n));
    for (int i = 0; i < n; i++) dj[i] = dijkstra(n, g, i);

    int L = 0, R = 1e9 + 1;
    while (R - L > 1) {
        int M = (L + R) / 2;
        vector<vector<int>> d(n, vector<int>(n, INF));
        for (int i = 0; i < n; i++) d[i][i] = 0;
        //cout << M << '\n';
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (dj[i][j] != INF) d[i][j] = dj[i][j] * M;
                for (int vt = 0; vt < n; vt++) {
                    if (dj[i][vt] != INF && dj[vt][j] != INF) {
                        d[i][j] = min(d[i][j], (dj[i][vt] + dj[vt][j]) * M - maxprof[vt][j]);
                    }
                }
            }
        }
        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]);
        bool loop = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (d[i][j] + d[j][i] <= 0) loop = true;
            }
        }
        if (loop) L = M;
        else R = M;
    }
    cout << L << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'std::vector<long long int> dijkstra(ll, std::vector<std::vector<std::pair<long long int, long long int> > >, ll)':
merchant.cpp:21:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |         auto [d, v] = *st.begin();
      |              ^
merchant.cpp:23:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         for (auto &[u, w] : g[v]) {
      |                    ^

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