Submission #292061

#	Time	Username	Problem	Language	Result	Execution time	Memory
292061		davooddkareshki	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	261 ms	4216 KiB

merchant

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

#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

typedef long long ll;
//typedef long double ld;

const int maxn = 105;
const int mod = 1e9+7;
const ll inf = 2e9+10;
const int MAX_K = 1010;

int n, m, k;
ll dis[maxn][maxn], W[maxn][maxn];
ll buy[maxn][MAX_K], sell[maxn][MAX_K];

ll dp[maxn][maxn];
bool ok(ll q)
{
    /// non_negetive cycle
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) dp[i][j] = -inf*inf;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j)
                dp[i][j] = (W[i][j] - dis[i][j] * q);

    for(int k = 1; k <= n; k++)
        for(int u = 1; u <= n; u++)
            for(int v = 1; v <= n; v++)
                dp[u][v] = max(dp[u][v], dp[u][k] + dp[k][v]);
    for(int v = 1; v <= n; v++)
        if(dp[v][v] >= 0) return 1;
    return 0;
}

signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> n >> m >> k;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++) dis[i][j] = inf;
        dis[i][i] = 0;
    }

    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, u, v, w; i <= m; i++)
    {
        cin>> u >> v >> w;
        dis[u][v] = min(dis[u][v], w);
    }

    /// floyd
    for(int k = 1; k <= n; k++)
        for(int u = 1; u <= n; u++)
            for(int v = 1; v <= n; v++)
                dis[u][v] = min(dis[u][v], dis[u][k] + dis[k][v]);
    /// end

    for(int u = 1; u <= n; u++)
    {
        for(int v = 1; v <= n; v++)
        {
            W[u][v] = 0.0;
            for(int x = 1; x <= k; x++)
                if(buy[u][x] != -1 && sell[v][x] != -1)
                    W[u][v] = max(W[u][v], -buy[u][x] + sell[v][x]);

         //   cout<< u <<" "<< v <<" "<< W[u][v] <<" "<< dis[u][v] <<"\n";
        }
    }

    ll lo = 0, hi = inf;
    while(hi-lo > 1)
    {
        ll tm = (hi + lo) >> 1;
        if(ok(tm)) lo = tm;
        else hi = tm;
    }

    cout<< lo;
}
/*
4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1
*/

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