Submission #261146

#	Time	Username	Problem	Language	Result	Execution time	Memory
261146		evpipis	Travelling Merchant (APIO17_merchant)	C++11	0 / 100	1 ms	256 KiB

merchant

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

typedef long long ll;

const int len = 205, max_k = 1005, inf = 1e9+10;
const ll long_inf = 1e18+10;

int n, m, k;
int dis[len][len], prof[len][len], buy[len][max_k], sell[len][max_k];
ll path[len][len], state[len];

bool check(int c){
    /*
    // this is for subtask 1

    for (int j = 1; j < n; j++)
        if (dis[0][j] != inf && dis[j][0] != inf)
            if (prof[0][j] - c*1LL*(dis[0][j]+dis[j][0]) >= 0)
                return true;

    return false;
    */



    /// ------------------------------------------------------------------------

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            path[i][j] = long_inf;
    //for (int i = 0; i < n; i++)
      //  path[i][i] = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dis[i][j] != inf)
                path[i][j] = c*1LL*dis[i][j] - prof[i][j];

    /*state[0] = 0;
    for (int i = 1; i < n; i++)
        state[i] = long_inf;

    for (int d = 0; d < n; d++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j && path[i][j] != long_inf && state[i]+path[i][j] <= state[j])
                    state[j] = state[i]+path[i][j];
    if (state[])

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && path[i][j] != long_inf && state[i]+path[i][j] <= state[j])
                return true;
    return false;*/

    for (int d = 0; d < n; d++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++){
                if (path[i][d] != long_inf && path[d][j] != long_inf)
                    path[i][j] = min(path[i][j], path[i][d]+path[d][j]);
                if (path[i][j] < -long_inf)
                    path[i][j] = -long_inf;
            }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && /*path[i][j] != long_inf && path[j][i] != long_inf &&*/ path[i][j]+path[j][i] <= 0)
                return true;
    return false;
    /// ------------------------------------------------------------------------

    // initialize path
    for (int i = 0; i < 2*n; i++)
        for (int j = 0; j < 2*n; j++)
            path[i][j] = long_inf; // here it is more than 1e18
    for (int i = 0; i < 2*n; i++)
        path[i][i] = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && dis[i][j] != inf)
                path[2*i][2*j+1] = c*1LL*dis[i][j] - prof[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (dis[i][j] != inf)
                path[2*i+1][2*j] = c*1LL*dis[i][j];

    // compute path
    for (int d = 0; d < 2*n; d++)
        for (int i = 0; i < 2*n; i++)
            for (int j = 0; j < 2*n; j++)
                if (dis[i][d] != long_inf && dis[d][j] != long_inf)
                    path[i][j] = min(path[i][j], path[i][d]+path[d][j]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j && path[2*i][2*j+1]+path[2*j+1][2*i] <= 0)
                return true;
    return false;
}

int bs(){
    int l = 1, r = 1e9, ans = 0;
    while (l <= r){
        int mid = (l+r)/2;
        if (check(mid))
            ans = mid, l = mid+1;
        else
            r = mid-1;
    }

    return ans;
}

int main(){
    freopen("0001-cycle-bydist0.in", "r", stdin);

    scanf("%d %d %d", &n, &m, &k);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            scanf("%d %d", &buy[i][j], &sell[i][j]);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dis[i][j] = inf; // here inf = 1e9+(something)
    //for (int i = 0; i < n; i++)
      //  dis[i][i] = 0;
    for (int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        dis[a-1][b-1] = c;
    }

    // fix dis, prof...
    for (int d = 0; d < n; d++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dis[i][d] != inf && dis[d][j] != inf)
                    dis[i][j] = min(dis[i][j], dis[i][d]+dis[d][j]);

    for (int a = 0; a < n; a++)
        for (int b = 0; b < n; b++)
            for (int d = 0; d < k; d++)
                if (buy[a][d] != -1 && sell[b][d] != -1)
                    prof[a][b] = max(prof[a][b], sell[b][d]-buy[a][d]);

    printf("%d\n", bs());
    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:117:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("0001-cycle-bydist0.in", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:122:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &buy[i][j], &sell[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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