제출 #1359682

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

merchant

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k;
    cin >> n >> m >> k;
    int graph[n][n];
    for(int i = 0;i<n;i++){
        fill(graph[i],graph[i]+n,inf);
    }
    int b[n][k];
    int s[n][k];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<k;j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(int i = 0;i<m;i++){
        int a,b,t;
        cin >> a >> b >> t;
        a--;b--;
        graph[a][b]=t;
    }
    for(int k = 0;k<n;k++){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    int prof[n][n];
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            prof[i][j]=0;
            for(int o = 0;o<k;o++){
                if(s[j][o]==-1||b[i][o]==-1)
                    continue;
                prof[i][j]=max(prof[i][j],s[j][o]-b[i][o]);
            }
        }
    }
    int lo = 0;
    int hi = inf;
    int temp[n][n];
    while(lo<hi){
        int mid = (lo+hi+1)/2;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n;j++){
                temp[i][j]=mid*min(graph[i][j],inf/mid)-prof[i][j];
            }
        }
        for(int k = 0;k<n;k++){
            for(int i = 0;i<n;i++){
                for(int j = 0;j<n;j++){
                    temp[i][j]=min(temp[i][j],temp[i][k]+temp[k][j]);
                }
            }
        }
        bool wor = 0;
        for(int i = 0;i<n;i++){
            if(temp[i][i]<=0){
                wor=1;
            }
        }
        if(wor){
            lo=mid;
        }
        else{
            hi=mid-1;
        }
    }
    cout << lo;
    return 0;
}

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