제출 #262510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262510		daniel920712	여행하는 상인 (APIO17_merchant)	C++14	0 / 100	51 ms	11512 KiB

merchant

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
vector < pair < long long , long long > > Next[200005];
vector < pair < long long , long long > > last[200005];
long long S[105][1005];
long long B[105][1005];
long long con[105][105];
bool have[105];
long long P[105][105];
long long Q[105][105];
priority_queue < pair < long long , long long > , vector < pair < long long , long long > > , greater < pair < long long , long long > > > all;
int main()
{
    long long N,M,K,a,b,c,ans=0,i,j,k;
    scanf("%lld %lld %lld",&N,&M,&K);
    for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]);
    while(M--)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        Next[a].push_back(make_pair(b,c));
        last[b].push_back(make_pair(a,c));
    }

    for(j=1;j<=N;j++)
    {
        for(i=1;i<=N;i++)
        {
            P[j][i]=0;
            Q[j][i]=1;
            con[j][i]=-1;
            have[i]=0;
        }
        all.push(make_pair(0,j));
        while(!all.empty())
        {
            if(have[all.top().second])
            {
                all.pop();
                continue;
            }
            have[all.top().second]=1;
            con[j][all.top().second]=all.top().first;
            for(auto i:Next[all.top().second]) all.push(make_pair(all.top().first+i.second,i.first));
            all.pop();
        }

    }


    for(i=1;i<=N;i++)
    {
        //printf("%lld %lld\n",in[i],out[i]);
        for(j=1;j<=N;j++)
        {
            P[i][j]=0;
            if(con[i][j]>0) Q[i][j]=con[i][j];
            else Q[i][j]=1e18;

            for(k=1;k<=K;k++)
            {
                if(con[j][k]!=-1&&S[j][k]!=-1&&B[i][k]!=-1&&S[j][k]>B[i][k]&&(double) (S[j][k]-B[i][k])/(double) con[i][j]>(double) P[i][j]/(double) Q[i][j])
                {
                    P[i][j]=(S[j][k]-B[i][k]);
                    Q[i][j]=con[i][j];
                }
            }
            //printf("%lld %lld %lld %lld\n",i,j,P[i][j],Q[i][j]);
        }
    }

    for(j=1;j<=N;j++)
    {
        for(k=1;k<=N;k++)
        {
            for(i=1;i<=N;i++)
            {
                if(con[i][k]==-1||con[k][j]==-1) continue;
                if((double) (P[i][k]+P[k][j])/(double) (Q[i][k]+Q[k][j])>(double) P[i][j]/(double) Q[i][j])
                {
                    P[i][j]=(P[i][k]+P[k][j]);
                    Q[i][j]=(Q[i][k]+Q[k][j]);
                    //printf("aa %lld %lld %lld %lld %lld %lld %lld %lld %lld\n",i,j,k,P[i][j],Q[i][j]);
                }
            }
        }
    }
    for(i=1;i<=N;i++)
    {
        //printf("%lld %lld\n",P[i][i],Q[i][i]);
        if(Q[i][i]) ans=max(ans,P[i][i]/Q[i][i]);
    }
    printf("%lld\n",ans);



    return 0;
}

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

merchant.cpp: In function 'int main()':
merchant.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     scanf("%lld %lld %lld",&N,&M,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:25:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]);
      |                                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |         scanf("%lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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