Submission #1260236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260236		damoon	Travelling Merchant (APIO17_merchant)	C++20	100 / 100	442 ms	3216 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define bg __int128
typedef pair<ll,ll> pii;
typedef pair<ll,pii> pip;
#define f first
#define s second
#define pb push_back

const ll L=110, L2=1010;
bg inf = 1;
const ll I=1e9+10;
int n,m,k;
ll S[L][L2],B[L][L2];
int bst[L][L];
vector<pip> edge,E;
bg dis[L][L],dd[L][L],D[L];

bool solve(ll x,int sr){
    if(x == 0)
        return 0;
    edge.clear();
    for(auto e:E){
        edge.pb(e);
        edge.back().f *= x;
    }

    for(int u=1;u<=n;u++){
        for(int v=1;v<=n;v++){
            if(bst[u][v] and dis[u][v] < I){
                ll w = x*dis[u][v] - (S[v][bst[u][v]]-B[u][bst[u][v]]);
                //cout<<u<<" --  "<<w<<"  --> "<<v<<"   "<<endl;
                edge.pb(pip(w,pii(u,v)));
            }
        }
    }

    for(int i=1;i<=n;i++){
        D[i] = inf;
    }
    D[sr] = 0;
    for(int i=1;i<=n+1;i++){
        for(auto e:edge){
            D[e.s.s] = min(D[e.s.s], D[e.s.f] + e.f);
        }
    }

    /*
    cout<<"D: ";
    for(int i=1;i<=n;i++){
        cout<<D[i]<<" ";
    }
    cout<<endl;
    */
    bool ok = 1;
    for(auto e:edge){
        ok = ok and (D[e.s.s] <= D[e.s.f]+e.f);
    }
    return !ok;
}

int main(){

    for(int i=1;i<=21;i++){
        inf *= 10;
    }
    
    //ifstream cin ("in.in");
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            cin>>B[i][j]>>S[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dis[i][j] = I;
        }
        dis[i][i] = 0;
    }
    for(int i=1;i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        E.pb(pip(w,pii(u,v)));
        dis[u][v] = w;
    }

    for(int w=1;w<=n;w++){
        for(int u=1;u<=n;u++){
            for(int v=1;v<=n;v++){
                dis[u][v] = min(dis[u][v], dis[u][w] + dis[w][v]);
            }
        }
    }

    for(int u=1;u<=n;u++){
        for(int v=1;v<=n;v++){
            if(u == v)
                continue;
            pii mx = pii(-I,0);
            for(int i=1;i<=k;i++){
                if(S[v][i] != -1 and B[u][i] != -1){
                    mx = max(mx,pii(S[v][i]-B[u][i],i));
                }
            }
            bst[u][v] = mx.s;
        }
    }

    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<"dis["<<i<<"]["<<j<<"]: "<<dis[i][j]<<endl;
        }
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<"bst["<<i<<"]["<<j<<"]: "<<bst[i][j]<<endl;
        }
    }
    */

    ll l=0,r=I;
    while(r-l > 1){
        ll mid = (l+r)/2;
        if(solve(mid,1))
            l = mid;
        else
            r = mid;
    }

    for(int i=1;i<=n;i++){
        solve(r,i);
        for(int j=1;j<=n;j++){
            dd[i][j] = D[j];
        }
    }

    bool ok = 0;
    for(auto e:edge){
        ok = ok or (dd[e.s.s][e.s.f] == -e.f);
    }

    cout<<l+ok<<endl;
}

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