Submission #919154

#	Time	Username	Problem	Language	Result	Execution time	Memory
919154		boris_mihov	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	54 ms	4184 KiB

merchant

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100 + 10;
const int MAXK = 1000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, m, k;
int vis[MAXN];
bool cycleEdge[MAXN][MAXN];
llong dist[MAXN][MAXN];
llong cost[MAXN][MAXN];
llong edge[MAXN][MAXN];
llong buy[MAXN][MAXK];
llong sell[MAXN][MAXK];
llong vals[MAXN];
llong cpy[MAXN];

bool dfs(int node)
{
    vis[node] = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!cycleEdge[node][i] || vis[i] == 2)
        {
            continue;
        }

        if (vis[i] == 1)
        {
            return true;
        }

        if (dfs(i))
        {
            return true;
        }
    }

    vis[node] = 2;
    return false;
}

bool check(llong c)
{
    for (int u = 1 ; u <= n ; ++u)
    {
        for (int v = 1 ; v <= n ; ++v)
        {
            if (dist[u][v] == INF)
            {
                edge[u][v] = INF;
            } else
            {
                edge[u][v] = c * dist[u][v] - cost[u][v];
            }
        }
    }

    std::fill(vals + 1, vals + 1 + n, INF);
    vals[1] = 0;

    for (int times = 1 ; times < n ; ++times)
    {
        for (int u = 1 ; u <= n ; ++u)
        {
            for (int v = 1 ; v <= n ; ++v)
            {
                if (vals[u] + edge[u][v] < vals[v])
                {
                    vals[v] = vals[u] + edge[u][v];
                }
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        cpy[i] = vals[i];
    }

    for (int u = 1 ; u <= n ; ++u)
    {
        for (int v = 1 ; v <= n ; ++v)
        {
            if (vals[u] + edge[u][v] < vals[v])
            {
                vals[v] = vals[u] + edge[u][v];
            }
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (vals[i] != cpy[i])
        {
            return true;
        }
    }

    for (int u = 1 ; u <= n ; ++u)
    {
        for (int v = 1 ; v <= n ; ++v)
        {
            cycleEdge[u][v] = (v != u && vals[v] == vals[u] + edge[u][v]);
        }
    }

    std::fill(vis + 1, vis + 1 + n, 0);
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!vis[i] && dfs(i))
        {
            return true;
        }
    }
    
    return false;
}

void solve()
{
    for (int mid = 1 ; mid <= n ; ++mid)
    {
        for (int from = 1 ; from <= n ; ++from)
        {
            if (from == mid) continue;
            for (int to = 1 ; to <= n ; ++to)
            {
                if (mid == to || from == to) continue;
                dist[from][to] = std::min(dist[from][to], dist[from][mid] + dist[mid][to]);
            }
        }
    }

    for (int u = 1 ; u <= n ; ++u)
    {
        for (int v = 1 ; v <= n ; ++v)
        {
            cost[u][v] = 0;
            for (int i = 1 ; i <= k ; ++i)
            {
                cost[u][v] = std::max(cost[u][v], sell[v][i] - buy[u][i]);
            }
        }
    }

    int l = 0, r = INTINF + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    std::cout << l << '\n';
}

void input()
{
    std::cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= k ; ++j)
        {
            std::cin >> buy[i][j] >> sell[i][j];
            if (buy[i][j] == -1)
            {
                buy[i][j] = INF;
            }

            if (sell[i][j] == -1)
            {
                sell[i][j] = 0;
            }
        }
    }

    std::fill(&dist[0][0], &dist[MAXN - 1][MAXN - 1] + 1, INF);
    for (int i = 1 ; i <= m ; ++i)
    {
        llong u, v, d;
        std::cin >> u >> v >> d;
        dist[u][v] = std::min(dist[u][v], d);
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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