제출 #653985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
653985		boris_mihov	여행하는 상인 (APIO17_merchant)	C++17	12 / 100	31 ms	2124 KiB

merchant

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <stack>
#include <cmath>

typedef long long llong;
const int MAXN = 100 + 10;
const int MAXK = 1000 + 10;
const int INF = 2e9;

int n, m, k;
llong dist[MAXN][MAXN];
llong profit[MAXN][MAXN];
llong b[MAXN][MAXK];
llong s[MAXN][MAXK];

bool bl[MAXN][MAXN];
std::pair <llong,llong> dp[MAXN][MAXN];
std::pair <llong,llong> f(int start, int curr)
{
    if (bl[start][curr])
    {
        return dp[start][curr];
    }

    bl[start][curr] = true;
    dp[start][curr] = {0, 1};
    if (start != curr && dist[curr][start] != 1e18)
    {
        dp[start][curr] = {profit[curr][start], dist[curr][start]};
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        if (i == start || i == curr || dist[curr][i] == 1e18 || dist[i][start] == 1e18) continue;
        llong currP = f(start, i).first;
        llong currQ = f(start, i).second;
        if (double(dp[start][curr].first / dp[start][curr].second) < double((currP + profit[curr][i]) / (currQ + dist[curr][i])))
        {
            dp[start][curr].first = currP + profit[curr][i];
            dp[start][curr].second = currQ + dist[curr][i];
        }
    }

    return dp[start][curr];
}

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

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            if (i == j) continue;
            for (int item = 1 ; item <= k ; ++item)
            {
                if (b[i][item] == -1 || s[j][item] == -1) continue;
                profit[i][j] = std::max(profit[i][j], s[j][item] - b[i][item]);
            }
        }
    }

    llong p = 0, q = 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        llong currP = f(i, i).first;
        llong currQ = f(i, i).second;
        if (p / q < currP / currQ)
        {
            p = currP;
            q = currQ;
        }
    }

    std::cout << p / q << '\n';
}

void read()
{
    std::cin >> n >> m >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= k ; ++j) 
        {
            std::cin >> b[i][j] >> s[i][j];
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= n ; ++j)
        {
            dist[i][j] = 1e18;
        }
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int x, y, d;
        std::cin >> x >> y >> d;
        dist[x][y] = d;
    }
}

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

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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