제출 #370724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
370724		mihai145	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	47 ms	2156 KiB

merchant

//
// Created by mihai145 on 24.02.2021.
//
 
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
const int NMAX = 100;
const int KMAX = 1000;
const long long INF = 1e9;
 
int N, M, K;
long long buy[NMAX + 2][KMAX + 2], sell[NMAX + 2][KMAX + 2];
 
long long bestProfit[NMAX + 2][NMAX + 2];
long long minTime[NMAX + 2][NMAX + 2];
 
void CalcBestProfit() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                //bestProfit[i][j] = 0;
                for (int k = 1; k <= K; k++) {
                    if (sell[j][k] != -1 && buy[i][k] != -1) {
                        bestProfit[i][j] = max(bestProfit[i][j], sell[j][k] - buy[i][k]);
                    }
                }
            }
        }
    }
}
 
void CalcMinTime() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                    if(minTime[i][k] != INF && minTime[k][j] != INF)
                        minTime[i][j] = min(minTime[i][j], minTime[i][k] + minTime[k][j]);
            }
        }
    }
}
 
vector<pair<int, long long>> g[NMAX + 2];
long long cost[NMAX + 2];
int impr[NMAX + 2];
bool inQ[NMAX + 2];
 
bool MoreThan(long long R) {
    for (int i = 1; i <= N; i++) {
        g[i].clear();
        cost[i] = INF;
        impr[i] = 0;
        inQ[i] = false;
 
        for (int j = 1; j <= N; j++) {
            g[i].push_back({j, -bestProfit[i][j] + R * minTime[i][j]});
        }
    }
 
    queue<int> q;
    q.push(1);
    cost[1] = 0;
    inQ[1] = true;
 
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inQ[node] = false;
 
        for (auto it : g[node]) {
            if (cost[it.first] > cost[node] + it.second) {
                cost[it.first] = cost[node] + it.second;
 
                if (!inQ[it.first]) {
                    q.push(it.first);
                    inQ[it.first] = true;
 
                    impr[it.first]++;
                    if (impr[it.first] > N) {
                        return true; ///NEGATIVE COST CYCLE
                    }
                }
            }
        }
    }
 
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N >> M >> K;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= K; j++) {
            cin >> buy[i][j] >> sell[i][j];
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            minTime[i][j] = INF;
        }
    }
    for (int i = 1; i <= M; i++) {
        int u, v, t;
        cin >> u >> v >> t;
        minTime[u][v] = t;
    }
 
    CalcBestProfit();
    CalcMinTime();
 
    /*
    cout << "BEST PROFIT\n";
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cout << bestProfit[i][j] << "   ";
        }
        cout << '\n';
    }
    cout << "\n\n\n";
 
    cout << "MIN TIME\n";
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cout << minTime[i][j] << "   ";
        }
        cout << '\n';
    }
    cout << "\n\n\n";
    */
 
    long long st = 0, dr = INF, sol = 0;
 
    while (st <= dr) {
        long long mid = (st + dr) >> 1;
 
        if (MoreThan(mid)) {
            sol = mid + 1;
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
 
    cout << sol << '\n';
    return 0;
}

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