Submission #155117

#	Time	Username	Problem	Language	Result	Execution time	Memory
155117		arnold518	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	113 ms	3452 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 = 1e9;

int N, M, K;
int B[MAXN+10][MAXK+10], S[MAXN+10][MAXK+10];
ll dist[MAXN+10][MAXN+10], adj[MAXN+10][MAXN+10], A[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(k=1; k<=N; k++) for(i=1; i<=N; i++) for(j=1; j<=N; j++) adj[i][j]=min(adj[i][k]+adj[k][j], adj[i][j]);
    for(i=1; i<=N; i++) if(adj[i][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<=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) continue;
        else for(k=1; k<=K; k++) if(B[i][k]!=-1 && S[j][k]!=-1) A[i][j]=max(A[i][j], (ll)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=1e9;
    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:52:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mid=lo+hi>>1;
                ~~^~~
merchant.cpp:30: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:31: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:37: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: 12 / 12
• Subtask 2: 21 / 21
• Subtask 3: 33 / 33
• Subtask 4: 34 / 34