제출 #743451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
743451		vjudge1	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	112 ms	2168 KiB

merchant

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18;
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n, m, k;
ll b[110][1010];
ll s[110][1010];
ll d[110][110];
ll c[110][110];
ll a[110][110];

bool ok(ll x){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == j) a[i][j] = -INF;
            else{
                a[i][j] = c[i][j];
                if(d[i][j] > 1e18 / x) a[i][j] -= 1e18;
                else a[i][j] -= d[i][j] * x;
            }
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                a[i][j] = max(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(a[i][i] >= 0) return 1;
    }
    return 0;
}

void test(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            d[i][j] = INF;
        }
    }
    for(int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = c;
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int t = 1; t <= k; t++){
                if(b[i][t] != -1 && s[j][t] != -1) c[i][j] = max(c[i][j], s[j][t] - b[i][t]);
            }
        }
    }
    ll ans = 0;
    for(ll l = 1, r = 1e18; l <= r;){
        ll mid = (l + r) >> 1;
        if(!ok(mid)) r = mid - 1;
        else l = mid + 1, ans = mid;
    }
    cout << ans;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

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