제출 #489640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489640		blue	여행하는 상인 (APIO17_merchant)	C++17	0 / 100	65 ms	2004 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

const ll INF = 1'000'000'001LL;
// const ll INF = 100;

int main()
{
    int N, M, K;
    cin >> N >> M >> K;

    vvll B(1+N, vll(1+K, INF));
    vvll S(1+N, vll(1+K, 0));
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= K; j++)
        {
            ll b, s;
            cin >> b >> s;
            if(b != -1) B[i][j] = b;
            if(s != -1) S[i][j] = s;
        }
    }

    vvll dist(1+N, vll(1+N, INF));
    for(int i = 1; i <= N; i++) dist[i][i] = 0;

    for(int e = 1; e <= M; e++)
    {
        int V, W;
        ll T;
        cin >> V >> W >> T;
        dist[V][W] = min(dist[V][W], T);
    }

    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    vvll profit(1+N, vll(1+N, 0));
    for(int u = 1; u <= N; u++)
        for(int v = 1; v <= N; v++)
            for(int j = 1; j <= K; j++)
                profit[u][v] = max(profit[u][v], S[v][j] - B[u][j]);


    // for(int u = 1; u <= N; u++) for(int v = 1; v <= N; v++) cerr << u << " -> " << v << " : " << dist[u][v] << ' ' << profit[u][v] << '\n';


    ll ans = 0;
    for(ll d = 1; d <= N; d++)
    {
        for(int u = 1; u <= N; u++)
        {
            for(int v = u+1; v <= N; v++)
            {
                if(dist[u][v] + dist[v][u] == d)
                {
                    ans = max(ans, (profit[u][v] + profit[v][u])/d);
                }
            }
        }
    }

    cout << ans << '\n';
}

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