Submission #1166426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166426		mariusharabari	Travelling Merchant (APIO17_merchant)	C++17	Compilation error	0 ms	0 KiB

merchant

#define ll long long
using namespace std;

const ll INF=LLONG_MAX/2;

int n, m, x;

ll b[101][1001], s[101][1001], g[101][101], g2[101][101], p[101][101];

void floyd_warshall(ll v[101][101]){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                v[j][k]=min(v[j][k],v[j][i]+v[i][k]);
}

int main(){
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            g[i][j]=INF;
        for(int j=1;j<=x;j++)
            cin>>b[i][j]>>s[i][j];
    }

    int u, v, c;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>c;
        g[u][v]=c;
    }

    floyd_warshall(g);


    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=x;k++)
                if(b[i][k]!=-1&&s[j][k]!=-1)
                    p[i][j]=max(p[i][j],s[j][k]-b[i][k]);


    ll l=1, r=1e9;
    while(l<=r){
        ll mid=(l+r)/2;
        //out<<mid<<endl;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g2[i][j]=mid*min(g[i][j],INF/mid)-p[i][j];

        floyd_warshall(g2);
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)
                cout<<g2[i][j]<<' ';
            cout<<endl;
        }*/
        bool ciclu=0;
        for(int i=1;i<=n;i++)
            if(g2[i][i]<=0)
                ciclu=1;

        if(ciclu)
            l=mid+1;
        else
            r=mid-1;
    }
    cout<<r;
    return 0;
}

Compilation message (stderr)

merchant.cpp:4:14: error: 'LLONG_MAX' was not declared in this scope
    4 | const ll INF=LLONG_MAX/2;
      |              ^~~~~~~~~
merchant.cpp:1:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
  +++ |+#include <climits>
    1 | #define ll long long
merchant.cpp: In function 'void floyd_warshall(long long int (*)[101])':
merchant.cpp:14:25: error: 'min' was not declared in this scope
   14 |                 v[j][k]=min(v[j][k],v[j][i]+v[i][k]);
      |                         ^~~
merchant.cpp: In function 'int main()':
merchant.cpp:18:5: error: 'cin' was not declared in this scope
   18 |     cin>>n>>m>>x;
      |     ^~~
merchant.cpp:1:1: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
  +++ |+#include <iostream>
    1 | #define ll long long
merchant.cpp:39:29: error: 'max' was not declared in this scope
   39 |                     p[i][j]=max(p[i][j],s[j][k]-b[i][k]);
      |                             ^~~
merchant.cpp:48:30: error: 'min' was not declared in this scope; did you mean 'mid'?
   48 |                 g2[i][j]=mid*min(g[i][j],INF/mid)-p[i][j];
      |                              ^~~
      |                              mid
merchant.cpp:66:5: error: 'cout' was not declared in this scope
   66 |     cout<<r;
      |     ^~~~
merchant.cpp:66:5: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?