제출 #1159602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159602		TroySer	여행하는 상인 (APIO17_merchant)	C++20	12 / 100	11 ms	2112 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const ll INF = 1e18;
const ld INF_DOUBLE = 1e18;

struct Market {
    vector<ll> B;
    vector<ll> S;
};

ll N, M, K;
ll v, w, t;

vector<Market> BSMarkets;
vector<vector<ll> > adjMat;
vector<vector<pair<ll, ll> > > adjList; // {neighbor, distance}

void takeInput() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N >> M >> K;
    BSMarkets.resize(N);
    for (ll i = 0; i < N; i++) {
        BSMarkets[i].B.resize(K);
        BSMarkets[i].S.resize(K);
        for (ll j = 0; j < K; j++) {
            cin >> BSMarkets[i].B[j] >> BSMarkets[i].S[j];
        }
    }

    adjList.resize(N);
    adjMat.resize(N, vector<ll>(N, INF));

    for (ll i = 0; i < M; i++) {
        cin >> v >> w >> t;
        v--; w--; 
        adjList[v].push_back({w, t});
        adjMat[v][w] = t;
    }

}

ll subtask1() {

    for (ll k = 0; k < N; k++) {
        for (ll i = 0; i < N; i++) {
            for (ll j = 0; j < N; j++) {
                adjMat[i][j] = min(adjMat[i][j], adjMat[i][k] + adjMat[k][j]);
            }
        }
    }

    vector<pair<ll, ll> > buyable; // {index, price}
    for (ll i = 0; i < K; i++) {
        if (BSMarkets[0].B[i] != -1) {
            buyable.push_back({i, BSMarkets[0].B[i]});
        }
    }

    ll bestPossible = 0;
    for (ll i = 0; i < N; i++) {
        if (i == 0) continue;
        for (auto item: buyable) {
            if (BSMarkets[i].S[item.first] == -1) continue;
            if (adjMat[0][i] == INF || adjMat[i][0] == INF) continue;
            ll currentDist = adjMat[0][i] + adjMat[i][0];
            bestPossible = max(bestPossible, (BSMarkets[i].S[item.first] - item.second) / currentDist);
        }
    }

    return bestPossible;

}

int main() {

    takeInput();

    ll res = subtask1();
    cout << res << endl;

}

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