제출 #631985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631985		s7mon	여행하는 상인 (APIO17_merchant)	C++17	21 / 100	145 ms	3292 KiB

merchant

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3 + 5;
const ll oo = 1e15;

int n, m, k;
ll buy[N][N], sell[N][N], d[N][N], c[N][N], f[N][N];

bool check(ll mid){
    for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++){
        f[i][j] = oo;
        if ( i != j && d[i][j] != oo )
            f[i][j] = min(f[i][j], -c[i][j]+mid*d[i][j]);
    }

    for (int t = 1; t <= n; t ++)
    for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        f[i][j] = min(oo, min(f[i][j], f[i][t]+f[t][j]));

    for (int i = 1; i <= n; i ++)
        if ( f[i][i] <= 0 ) return true;

    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    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 ++)
        if ( i == j ) d[i][j] = 0;
        else d[i][j] = oo;

    for (int i = 1; i <= m; i ++){
        int u, v;
        ll w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
    }

    for (int t = 1; t <= n; t ++)
    for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        d[i][j] = min(d[i][j], d[i][t]+d[t][j]);

    for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++) if ( i != j ){
        for (int t = 1; t <= k; t ++) if ( buy[i][t] != -1 && sell[j][t] != -1 )
            c[i][j] = max(c[i][j], sell[j][t]-buy[i][t]);
    }

    ll lo = 1, hi = 1e15, res = 0;
    while ( lo <= hi ){
        ll mid = ( lo + hi ) / 2;
        if ( check(mid) ) res = mid, lo = mid + 1;
        else hi = mid - 1;
    }

    cout << res;

    return 0;
}

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