제출 #1345717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1345717		StefanSebez	여행하는 상인 (APIO17_merchant)	C++20	100 / 100	35 ms	1476 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
template<typename T1,typename T2>void chmn(T1 &x,const T2 &y){x=x<y?x:y;}
template<typename T1,typename T2>void chmx(T1 &x,const T2 &y){x=x>y?x:y;}
const int N=110,M=1010,inf=1e9;
const ll INF=1LL<<60;
int n,m,K,B[N][M],S[N][M];
ll dist[N][N],dist1[N][N],d[N][N];
bool check(ll mid){
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(INF,mid*dist[i][j])-dist1[i][j];
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        chmn(d[i][j],d[i][k]+d[k][j]);
        chmx(d[i][j],-INF);
    }
    for(int i=1;i<=n;i++)if(d[i][i]<=0)return true;
    return false;
}
int main(){
    scanf("%i%i%i",&n,&m,&K);
    for(int i=1;i<=n;i++)for(int j=1;j<=K;j++){
        scanf("%i%i",&B[i][j],&S[i][j]);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j]=2*inf;
    for(int i=1;i<=m;i++){
        int u,v,w;scanf("%i%i%i",&u,&v,&w);
        dist[u][v]=w;
    }
    for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        chmn(dist[i][j],dist[i][k]+dist[k][j]);
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=K;k++){
        if(S[j][k]!=-1&&B[i][k]!=-1)chmx(dist1[i][j],S[j][k]-B[i][k]);
    }
    ll l=0,r=inf,res=0;
    while(l<=r){
        ll mid=l+r>>1;
        if(check(mid))l=mid+1,res=mid;
        else r=mid-1;
    }
    printf("%lld\n",res);
    return 0;
}

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

merchant.cpp: In function 'int main()':
merchant.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%i%i%i",&n,&m,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%i%i",&B[i][j],&S[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:31:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         int u,v,w;scanf("%i%i%i",&u,&v,&w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~

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