Submission #155095

#	Time	Username	Problem	Language	Result	Execution time	Memory
155095		arnold518	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	136 ms	3108 KiB

merchant

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 100;
const int MAXM = 9900;
const int MAXK = 1000;
const ll INF = 1e12;

int N, M, K;
int B[MAXN+10][MAXK+10], S[MAXN+10][MAXK+10], A[MAXN+10][MAXN+10];
ll dist[MAXN+10][MAXN+10], adj[MAXN+10][MAXN+10];

bool decide(ll X)
{
    int i, j, k;

    for(i=1; i<=N; i++) for(j=1; j<=N; j++) adj[i][j]=X*dist[i][j]-A[i][j];
/*
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=N; j++) printf("%lld ", adj[i][j]);
        printf("\n");
    }
    printf("====================%lld\n", X);
*/
    for(k=1; k<=N; k++) for(i=1; i<=N; i++) for(j=1; j<=N; j++) if(adj[i][k]!=INF && adj[k][j]!=INF) adj[i][j]=min(adj[i][k]+adj[k][j], adj[i][j]);
    /*
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=N; j++) printf("%lld ", adj[i][j]);
        printf("\n");
    }
    printf("====================!%lld\n", X);*/
    for(i=1; i<=N; i++) for(j=1; j<=N; j++) if(i!=j && adj[i][j]+adj[j][i]<=0) return true;
    return false;
}

int main()
{
    int i, j, k;

    scanf("%d%d%d", &N, &M, &K);
    for(i=1; i<=N; i++) for(j=1; j<=K; j++) scanf("%d%d", &B[i][j], &S[i][j]);

    for(i=1; i<=N; i++) for(j=1; j<=N; j++) dist[i][j]=INF;
    for(i=1; i<=N; i++) dist[i][i]=0;

    for(i=1; i<=M; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v]=w;
    }

    for(i=1; i<=N; i++) for(j=1; j<=N; j++)
    {
        if(i==j)
        {
            for(k=1; k<=K; k++) if(B[i][k]!=-1 && S[j][k]!=-1) A[i][j]+=max(S[j][k]-B[i][k], 0);
        }
        else
        {
            for(k=1; k<=K; k++) if(B[i][k]!=-1 && S[j][k]!=-1) A[i][j]=max(A[i][j], S[j][k]-B[i][k]);
        }
    }

    for(k=1; k<=N; k++) for(i=1; i<=N; i++) for(j=1; j<=N; j++) if(dist[i][k]!=INF && dist[k][j]!=INF) dist[i][j]=min(dist[i][k]+dist[k][j], dist[i][j]);

    ll lo=0, hi=1e15;
    while(lo+1<hi)
    {
        ll mid=lo+hi>>1;
        if(decide(mid)) lo=mid;
        else hi=mid;
    }
    printf("%lld", lo);
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:76:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mid=lo+hi>>1;
                ~~^~~
merchant.cpp:46: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:47:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) for(j=1; j<=K; j++) scanf("%d%d", &B[i][j], &S[i][j]);
                                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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