Submission #625970

#	Time	Username	Problem	Language	Result	Execution time	Memory
625970		socpite	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	428 ms	6076 KiB

merchant

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

#define f first
#define s second

typedef long long ll;

const int maxn = 1005;
const ll inf = 1e18;

ll w[maxn][maxn], d[maxn][maxn], d2[maxn][maxn], best[maxn][maxn], prc[2][maxn][maxn];

int n, m, K;

bool chk(ll x){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(d[i][j] < inf){
                d2[i][j] = d[i][j]*x - best[i][j];
                d2[i+n][j+n] = d2[i][j];
                if(i != j){
                    d2[i+n][j] = d2[i][j];
                    d2[i][j+n] = d2[i][j];
                }
                else{
                    d2[i+n][j] = inf;
                    d2[i][j+n] = inf;
                }
            }
            else {
                d2[i][j] = inf;
                d2[i][j+n] = inf;
                d2[i+n][j] = inf;
                d2[i+n][j+n] = inf;
            }
        }
    }
    for(int k = 1; k <= 2*n; k++){
        for(int i = 1; i <= 2*n; i++){
            for(int j = 1; j <= 2*n; j++)if(d2[i][k] < inf && d2[k][j] < inf)d2[i][j] = min(d2[i][j], d2[i][k]+d2[k][j]);
        }
    }
    for(int i = 1; i <= n; i++){
        //cout << x << " " << i << " " << d2[i][i+n] << endl;
        if(d2[i][i+n] <= 0)return 1;
    }
    return 0;
}

int main(){
    cin >> n >> m >> K;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= K; j++){
            for(int l = 0; l < 2; l++)cin >> prc[l][i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)d[i][j] = i == j ? 0 : inf;
    }
    for(int i = 0; i < m; i++){
        ll a, b, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w);
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; 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++){
            if(d[i][j] < inf){
                for(int l = 1; l <= K; l++){
                    if(prc[0][i][l] >= 0 && prc[1][j][l] > 0)best[i][j] = max(best[i][j], prc[1][j][l] - prc[0][i][l]);
                }
            }
        }
    }
    ll l = 0, r = 1e9;
    while(l < r){
        ll mid = (l+r+1)>>1;
        if(chk(mid))l = mid;
        else r = mid-1;
    }
    cout << l;
}

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