제출 #1368078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1368078		ChottuF	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	50 ms	2248 KiB

merchant

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 105;
const int MAXV = 1e18;
const int MINV = -1e18;

int dist[MAXN][MAXN];
int prof[MAXN][MAXN];
int work[MAXN][MAXN];

bool check(int mid, int n){
    for (int i = 0; i<n; i++){
        for (int j = 0; j<n; j++){
            
            if (dist[i][j] >= MAXV) work[i][j] = MINV;
            else work[i][j] = prof[i][j] - (mid * dist[i][j]);
        }
    }
    
    for (int k = 0; k<n; k++){
        for (int i = 0; i<n; i++){
            for (int j = 0; j<n; j++){
                if (work[i][k] <= MINV || work[k][j] <= MINV) continue;
                work[i][j] = max(work[i][j], work[i][k] + work[k][j]);
            }
        }
    }
    
    for (int i = 0; i<n; i++){
        if (work[i][i] >= 0) return true;
    }
    return false;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i<MAXN; i++){
        for (int j = 0; j<MAXN; j++){
            dist[i][j] = MAXV;
            //dist[i][i] = 0;
        }
    }
    
    
    int n,m,k;
    cin >> n >> m >> k;
    int b[n][k] , s[n][k];
    for (int i = 0; i<n; i++){
        for (int v = 0; v<k; v++){
            cin >> b[i][v] >> s[i][v];
        }
    }
    for (int i = 0; i<m; i++){
        int v,w,t;
        cin >> v >> w >> t;
        v--;w--;
        dist[v][w] = min(dist[v][w], t);
    }
    for (int k = 0; k<n; k++){
        for (int i = 0; i<n; i++){
            for (int j = 0; j<n; j++){
                if (dist[i][k] + dist[k][j] <= dist[i][j]){
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    for (int i = 0; i<n; i++){
        for (int j = 0; j<n; j++){
            if (i == j) continue;
            for (int v = 0; v<k; v++){
                if (b[i][v] == -1 || s[j][v] == -1) continue;
                int val = s[j][v]-b[i][v];
                prof[i][j] = max(prof[i][j], val);
            }
        }
    }
    
    int lo = 0;
    int hi = 1e9;
    int bst = lo;
    while (lo <= hi){
        int mid = (lo+hi)/2;
        if (check(mid, n)){
            lo = mid+1;
            bst = max(bst, mid);
        }
        else{
            hi = mid-1;
        }
    }
    cout << bst;
    return 0;
}

• 서브태스크 1: 12 / 12
• 서브태스크 2: 21 / 21
• 서브태스크 3: 33 / 33
• 서브태스크 4: 34 / 34