Submission #1260762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260762		Sam_arvandi	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	223 ms	2444 KiB

merchant

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

typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;
#define FOR(i, j, n) for(ll i= 1; i<= n; i++)
#define ROF(i, n, j) for(ll i = n; i>= j; i--)
#define F first
#define S second
#define pb push_back
#define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define G(i, j) get<j-1>(i)
#define prll(x) cout << #x << ": " << x << endl

const ll mn = 100 + 5, mk = 1000 + 5, inf = 1e16;
ll d[mn], y[mn][mn], b[mn][mk], f[mn][mn], c[mn][mk], D[mn][mn];
ld a[mn][mn], d2[mn], q[mn];
bool mark[mn];

signed main()
{
        IOS;
        ll w, n, m, k, u, v;
        cin >> n >> m >> k;
        FOR(i, 1, n)
        {
                FOR(j, 1, k)
                {
                        cin >> b[i][j] >> c[i][j];
                        if (b[i][j] == -1) b[i][j] = inf;
                        if (c[i][j] == -1) c[i][j] = -inf;
                }
        }
        FOR(i,1, n)
        {
                FOR(j, 1, n)
                {
                        y[i][j] = inf;
                }
        }
        FOR(i, 1, m)
        {
                cin >> u >> v >> w;
                y[u][v] = w;
        }
        FOR(i,1 , n)
        {
                FOR(j, 1, n)
                {
                        FOR(w, 1, k)
                        {
                                f[i][j] = max(f[i][j], -b[i][w]+c[j][w]);
                        }
                }
        }
        FOR(r, 1, n)
        {
                FOR(i, 1, n)
                {
                        mark[i] = 0;
                        d[i] = inf;
                }
                d[r] = 0;
                FOR(tmp, 1, n)
                {
                        u = -1;
                        FOR(i, 1, n)
                        {
                                if (u == -1 and !mark[i]) u = i;
                                if (!mark[i] and d[u] > d[i]) u = i;
                        }
                        mark[u] = 1;
                        FOR(v, 1, n)
                        {
                                if (mark[v]) continue;
                                d[v] = min(d[v], d[u]+y[u][v]);
                        }
                }
                FOR(i, 1, n)
                {
                        D[r][i] = d[i];
                }
        }
        /*
        FOR(i, 1, n)
        {
                FOR(j, 1, n)
                {
                        cout << i << ' ' << j << ' ' << f[i][j] << endl;
                }
        }
        cout <<"_----------------" << endl;
        */
        ll L = 0, R = inf, mid;
        while (L+1 != R)
        {
                mid = (L+R)/2;
                FOR(u, 1, n)
                {
                        FOR(v, 1, n)
                        {
                                if (u == v)
                                {
                                        a[u][v] = inf;
                                        continue;
                                }
                                a[u][v] = -f[u][v] +mid*D[u][v] - (0.000000001);
                        }
                }
                FOR(i, 1, n) d2[i] = 0;
                FOR(tmp, 1, n+2)
                {
                        FOR(u, 1, n)
                        {
                                FOR(v, 1, n)
                                {
                                        d2[v] = min(d2[v], d2[u]+a[u][v]);
                                }
                        }
                        if (tmp == n+1)
                        {
                                FOR(u, 1, n) q[u] = d2[u];
                        }
                }
                bool flag = 0;
                FOR(u, 1, n)
                {
                        if (q[u] != d2[u]) flag = 1;
                }
                if (flag) L = mid;
                else R = mid;
        }
        cout << L;
        return 0;
}

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