Submission #1034497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034497		andrei_iorgulescu	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	127 ms	7508 KiB

merchant

#include <bits/stdc++.h>
 
using namespace std;
 
using ld = long double;
using ll = long long;
 
ld eps = 0.00000000001d;
 
int n,m,k;
int b[105][1005],s[105][1005];
int d[105][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];
 
bool ciclu_negativ()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        inq[i] = true,nrq[i] = 1,dist[i] = 0,q.push(i);
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        inq[nod] = false;
        for (auto vecin : g[nod])
        {
            if (dist[vecin.first] > dist[nod] + vecin.second)
            {
                dist[vecin.first] = dist[nod] + vecin.second;
                if (!inq[vecin.first])
                {
                    inq[vecin.first] = true;
                    nrq[vecin.first]++;
                    q.push(vecin.first);
                    if (nrq[vecin.first] > n)
                        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] = (f[i][j] / (ld)t) - (ld)d[n][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++)
    {
        g[i].clear();
        for (int j = 1; j <= n; j++)
            if (i != j and d[n][i][j] != -1)
                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++)
            for (int ii = 0; ii <= n; ii++)
                d[ii][i][j] = -1;
    for (int i = 1; i <= n; i++)
        d[0][i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int x,y,cost;
        cin >> x >> y >> cost;
        d[0][x][y] = cost;
    }
    for (int kk = 1; kk <= n; kk++)
    {
        for (int x = 1; x <= n; x++)
        {
            for (int y = 1; y <= n; y++)
            {
                if (x == y)
                    d[kk][x][y] = 0;
                else
                {
                    d[kk][x][y] = d[kk - 1][x][y];
                    if (d[kk - 1][x][kk] != -1 and d[kk - 1][kk][y] != -1)
                        if (d[kk - 1][x][kk] + d[kk - 1][kk][y] < d[kk][x][y] or d[kk][x][y] == -1)
                            d[kk][x][y] = d[kk - 1][x][kk] + d[kk - 1][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