oj.uz

답안 #95772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95772 2019-02-02T13:48:55 Z Bodo171 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 1000 ms 126840 KB 
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#define mp make_pair
using namespace std;
const int nmax=105;
const int kmax=1005;
queue< pair<int,int> > q;
vector<int> v[nmax];
long long cost[nmax][nmax];
long long d[nmax][kmax],prof[nmax][kmax],pret[nmax][kmax];
int viz[nmax][kmax];
int n,k,m,nod,item,nxt,i,j,a,b,c;
long long p,ans;
bool check(long long x)
{
    while(!q.empty()) q.pop();
    q.push({0,0});
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
           viz[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
          d[i][j]=LLONG_MIN;
          cout<<x<<'\n';
    while(!q.empty())
    {
        nod=q.front().first;item=q.front().second;
        q.pop();
        for(int nxt=1;nxt<=n;nxt++)
            if(nxt!=nod&&cost[nod][nxt]<=1LL*1000*1000*1000)
        {
            if(d[nod][item]-1LL*x*cost[nod][nxt]>=d[nxt][item])
            {
                d[nxt][item]=d[nod][item]-1LL*x*cost[nod][nxt];
                q.push(mp(nxt,item));
                viz[nxt][item]++;
                if(viz[nxt][item]>=n*(k+1)+1)
                    return 1;
            }
            if(item)
            {
                if(d[nod][item]+1LL*prof[nxt][item]-1LL*x*cost[nod][nxt]>=d[nxt][0]&&prof[nxt][item]!=-1)
                {
                    d[nxt][0]=d[nod][item]-1LL*x*cost[nod][nxt]+1LL*prof[nxt][item];
                    q.push({nxt,0});
                    viz[nxt][0]++;
                    if(viz[nxt][0]>=n*(k+1)+1)
                        return 1;
                }
            }
        }
        if(!item)
        {
            for(int i=1;i<=k;i++)
             if(d[nod][0]-1LL*pret[nod][i]>=d[nod][i]&&pret[nod][i]!=-1)
             {
                 d[nod][i]=d[nod][0]-1LL*pret[nod][i];
                 q.push({nod,i});
                 viz[nod][i]++;
                 if(viz[nod][i]>=n*(k+1)+1)
                    return 1;
             }
        }
    }
    return 0;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
    {
        pret[i][0]=-1,prof[i][0]=-1;
        for(j=1;j<=k;j++)
        {
            cin>>pret[i][j];
            cin>>prof[i][j];
        }
    }
    for(i=1;i<=k;i++)
        pret[0][i]=prof[0][i]=-1;
    for(i=1;i<=n;i++)
       for(j=1;j<=n;j++)
        if(i!=j)
         cost[i][j]=1LL*1e16;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        cost[a][b]=min(cost[a][b],1LL*c);
    }
    int kt;
    for(kt=1;kt<=n;kt++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
               if(cost[i][kt]+cost[kt][j]<cost[i][j])
                  cost[i][j]=cost[i][kt]+cost[kt][j];
    for(p=30;p>=0;p--)
        if(check(ans+(1LL<<p)))
          ans+=(1LL<<p);
    cout<<ans;
    return 0;
}

Compilation message

merchant.cpp: In function 'bool check(long long int)':
merchant.cpp:24:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for(int j=0;j<=k;j++)
         ^~~
merchant.cpp:26:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
           cout<<x<<'\n';
           ^~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 126840 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 1904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1055 ms 37960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 1904 KB Output isn't correct
2 Halted 0 ms 0 KB -