Submission #1034461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034461		andrei_iorgulescu	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	232 ms	3932 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

using ld = long double;
using ll = long long;

ld eps = 1e-15d;
ld inf = 1e18;

int n,m,k;
int b[105][1005],s[105][1005];
int d[105][105];
int f[105][105];
ld cost[105][105];
vector<pair<int,ld>> g[105];

bool inq[105];
int nrq[105];
ld dist[105];

ld dd[105][105];

bool ciclu_negativ()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dd[i][j] = cost[i][j];
    for (int i = 1; i <= n; i++)
        dd[i][i] = 0;
    for (int kk = 1; kk <= n; kk++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dd[i][j] = min(dd[i][j],dd[i][kk] + dd[kk][j]);
    for (int i = 1; i <= n; i++)
        if (dd[i][i] < 0)
            return true;
    return false;
}

bool pot(int t)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cost[i][j] = ((ld)f[i][j] / (ld)t) - (ld)d[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cost[i][j] = -cost[i][j] - eps;
    for (int i = 1; i <= n; i++)
        cost[i][i] = 0;
    for (int i = 1; i <= n; i++)
    {
        g[i].clear();
        for (int j = 1; j <= n; j++)
            if (i != j)
                g[i].push_back({j,cost[i][j]});
    }
    return ciclu_negativ();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    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; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                d[i][j] = 1e9;
    for (int i = 1; i <= m; i++)
    {
        int x,y,cost;
        cin >> x >> y >> cost;
        d[x][y] = cost;
    }
    for (int kk = 1; kk <= n; kk++)
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
                d[x][y] = min(d[x][y],d[x][kk] + d[kk][y]);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
            {
                for (int q = 1; q <= k; q++)
                {
                    if (b[i][q] != -1 and s[j][q] != -1)
                        f[i][j] = max(f[i][j],s[j][q] - b[i][q]);
                }
            }
        }
    }
    int st = 0, pas = 1 << 29;
    while (pas != 0)
    {
        if (pot(st + pas))
            st += pas;
        pas /= 2;
    }
    cout << st;
    return 0;
}

/**
Fie f(i,j) = practic costul maxim pe care il fac mergand de la i la j (direct route), L(i,j) = lungimea drumului
L(i,j) calculez in n^3 cu floyd, f(i,j) in n^2k

Caut binar raspunsul, sa zicem ca incerc >= T. f(i,j) /= T, f(i,j) -= L(i,j), f(i,j) = -f(i,j), f(i,j) -= 0.0000001. Acum doar caut un ciclu negativ
Pentru asta, bellman-ford si am O(B * log), unde B este bellman ford-ul care parca era bounded by N * M deci N^3log pe worst case
**/

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