제출 #155109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155109		mhy908	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	119 ms	4472 KiB

merchant

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define llinf 987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
int n, m, k;
LL buy[110][1010], sell[110][1010];
LL floyd[110][110];
LL cost[110][110];
LL edge[110][110];
bool negcycle()
{
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(edge[i][j]>edge[i][k]+edge[k][j]){
                    edge[i][j]=edge[i][k]+edge[k][j];
                }
            }
        }
    }
    bool ret=false;
    for(int i=1; i<=n; i++){
        if(edge[i][i]<=0)ret=true;
    }
    return ret;
}
LL binsearch(LL a, LL b){
    if(a==b)return a;
    LL mid=(a+b)/2+1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            edge[i][j]=min((LL)inf, mid*floyd[i][j]-cost[i][j]);
        }
    }
    if(negcycle())return binsearch(mid, b);
    return binsearch(a, mid-1);
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++)
            scanf("%lld %lld", &buy[i][j], &sell[i][j]);
    for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)floyd[i][j]=inf;
    for(int i=1; i<=m; i++){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        floyd[a][b]=min(floyd[a][b], c);
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(floyd[i][j]>floyd[i][k]+floyd[k][j]){
                    floyd[i][j]=floyd[i][k]+floyd[k][j];
                }
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int z=1; z<=k; z++){
                if(sell[j][z]>=0&&buy[i][z]>=0)cost[i][j]=max(cost[i][j], sell[j][z]-buy[i][z]);
            }
        }
    }
    printf("%lld", binsearch(0, (LL)inf));
}

컴파일 시 표준 에러 (stderr) 메시지

merchant.cpp: In function 'int main()':
merchant.cpp:44: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:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld %lld", &buy[i][j], &sell[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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