Submission #456320

#	Time	Username	Problem	Language	Result	Execution time	Memory
456320		prvocislo	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	45 ms	2368 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;

const ll inf = 1e18 + 5;
const int maxn = 105;
int n, m, k;
void floyd_warshall(vector<vector<ll> >& d)
{
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++)
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
vector<vector<ll> > d(maxn, vector<ll>(maxn, inf)), z(maxn, vector<ll>(maxn, 0)), b(maxn, vector<ll>(maxn)), s(maxn, vector<ll>(maxn));
bool check(ll X) // true ak existuje dobry cyklus (mozeme hladat vyssie)
{
    vector<vector<ll> > dist(n, vector<ll>(n, inf));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (d[i][j] != inf)
        dist[i][j] = X * d[i][j] - z[i][j];
    floyd_warshall(dist);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) 
        if (i != j && dist[i][j] + dist[j][i] <= 0) return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) for (int j = 0; j < k; j++) 
        cin >> b[i][j] >> s[i][j];
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int i = 0, u, v, t; i < m; i++)
        cin >> u >> v >> t, d[--u][--v] = t;
    floyd_warshall(d);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j && d[i][j] != inf)
        for (int ki = 0; ki < k; ki++) if (b[i][ki] != -1 && s[j][ki] != -1)
            z[i][j] = max(z[i][j], s[j][ki] - b[i][ki]);
    ll lo = 0, hi = 1e9 + 5;
    while (lo < hi)
    {
        ll mi = (lo + hi + 1) >> 1;
        if (check(mi)) lo = mi;
        else hi = mi - 1;
    }
    cout << lo << "\n";
    return 0;
}

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