oj.uz

답안 #95783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95783 2019-02-02T14:51:40 Z Bodo171 여행하는 상인 (APIO17_merchant) C++14
33 / 100
 82 ms 2144 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< int > q;
vector<int> v[nmax];
long long cost[nmax][nmax],wn[nmax][nmax];
long long d[nmax],prof[nmax][kmax],pret[nmax][kmax];
int viz[nmax],inq[nmax];
int n,k,m,nod,item,nxt,i,j,a,b,c,ind;
long long p,ans;
bool check(long long x)
{
    while(!q.empty()) q.pop();
    q.push(0);
    for(int i=0;i<=n;i++)
           viz[i]=inq[i]=0;
    for(int i=1;i<=n;i++)
          d[i]=LLONG_MIN;
    while(!q.empty())
    {
        nod=q.front();inq[nod]=0;
        q.pop();
        for(int nxt=1;nxt<=n;nxt++)
            if(nxt!=nod&&cost[nod][nxt]<=1LL*1000*1000*1000)
        {
            if(d[nod]+wn[nod][nxt]-1LL*x*cost[nod][nxt]>=d[nxt])
            {
                if(!inq[nxt])
                {
                    q.push(nxt);
                    inq[nxt]=1;
                }
                d[nxt]=d[nod]+wn[nod][nxt]-1LL*x*cost[nod][nxt];
                viz[nxt]++;
                if(viz[nxt]>=n)
                    return 1;
            }
        }
    }
    return 0;
}
void bf(int s)
{
    q.push(s);
    while(!q.empty())
    {
        nod=q.front();q.pop();
        for(i=0;i<v[nod].size();i++)
        {
            nxt=v[nod][i];
            if(cost[s][nod]+cost[nod][nxt]<cost[s][nxt])
            {
                cost[s][nxt]=cost[s][nod]+cost[nod][nxt];
                q.push(nxt);
            }
        }
    }
}
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<=n;i++)
        for(j=1;j<=n;j++)
          for(ind=1;ind<=k;ind++)
             if(pret[i][ind]!=-1&&prof[j][ind]!=-1)
                wn[i][j]=max(wn[i][j],prof[j][ind]-pret[i][ind]);
    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);
        v[a].push_back(b);
    }
    int kt;
    for(int s=1;s<=n;s++)
        bf(s);
    for(p=30; p>=0; p--)
        if(check(ans+(1LL<<p)))
            ans+=(1LL<<p);
    cout<<ans;
    return 0;
}

Compilation message

merchant.cpp: In function 'void bf(int)':
merchant.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<v[nod].size();i++)
                 ~^~~~~~~~~~~~~~
merchant.cpp: In function 'int main()':
merchant.cpp:95:9: warning: unused variable 'kt' [-Wunused-variable]
     int kt;
         ^~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2040 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 40 ms 1144 KB Output is correct
4 Incorrect 2 ms 760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 1528 KB Output is correct
2 Correct 82 ms 2144 KB Output is correct
3 Correct 31 ms 1400 KB Output is correct
4 Correct 17 ms 1528 KB Output is correct
5 Correct 61 ms 1528 KB Output is correct
6 Correct 26 ms 1400 KB Output is correct
7 Correct 5 ms 892 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 10 ms 888 KB Output is correct
10 Correct 6 ms 888 KB Output is correct
11 Correct 7 ms 888 KB Output is correct
12 Correct 5 ms 888 KB Output is correct
13 Correct 4 ms 888 KB Output is correct

Subtask #4
0 / 34.0

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