제출 #1180269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180269		NValchanov	여행하는 상인 (APIO17_merchant)	C++20	21 / 100	52 ms	840 KiB

merchant

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e2 + 10;
const ll INF = 4e18 + 10;

int n, m, t;
ll buy[MAXN][MAXN];
ll sell[MAXN][MAXN];

vector < vector < ll > > org;
vector < vector < ll > > fake;
ll prof[MAXN][MAXN];

void read()
{
    cin >> n >> m >> t;

    org.resize(n + 1);
    fake.resize(n + 1);
    for(int i = 0; i <= n; i++)
    {
        org[i].resize(n + 1, INF);
        fake[i].resize(n + 1, INF);
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= t; j++)
        {
            cin >> buy[i][j] >> sell[i][j];
        }
    }

    for(int i = 1; i <= m; i++)
    {
        int u, v;
        ll cost;

        cin >> u >> v >> cost;
        org[u][v] = cost;
    }
}

void floyd(vector < vector < ll > > &g)
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

void find_prof()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= t; k++)
            {
                if(buy[i][k] == -1 || sell[j][k] == -1)
                    continue;

                prof[i][j] = max(prof[i][j], -buy[i][k] + sell[j][k]);
            }
        }
    }
}

bool check(ll x)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            fake[i][j] = x * min(INF / x, org[i][j]) - prof[i][j];
        }
    }

    floyd(fake);

    for(int i = 1; i <= n; i++)
    {
        if(fake[i][i] <= 0)
            return true;
    }

    return false;
}

void solve()
{
    ll left = 0;
    ll right = 1e9 + 10;
    ll mid;

    while(right - left > 1)
    {
        mid = left + (right - left) / 2;

        if(check(mid))
            left = mid;
        else
            right = mid;
    }

    cout << left << endl;
}

int main()
{    
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    

    read();
    floyd(org);
    find_prof();
    solve();

    return 0;
}

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